作者:
Aa841018 (andrew)
2019-09-01 15:11:46https://i.imgur.com/tu5Vo8A.jpg
請問2.（2） （106交大）
題目：A是NP則必定存在一個NP algo B可解A
這題為什麼是T啊？
作者:
JKLee (J.K.Lee)
2019-09-01 16:28:00因為NPC的存在
作者:
mistel (Mistel)
2019-09-01 18:07:00樓上說的是指所有NP都可以歸約到NPC的意思嗎？
作者:
Aa841018 (andrew)
2019-09-01 18:15:00可是題目沒特別說NPC存在……
作者:
mistel (Mistel)
2019-09-01 18:47:00NPC一定存在...圖同構問題，Hamilton，3SAT都是啊
作者:
Aa841018 (andrew)
2019-09-02 18:05:00可是雖然所有np都可reduce到npc，但沒人保證npc一定可以被解決啊！
作者:
mistel (Mistel)
2019-09-02 18:24:00NPC蒐集的不是不能被解決的問題，而是認為沒有多項式時間解法的問題，因為一定都有暴力解存在，而且NPC其實是NP跟NP-Hard的交集
作者:
firejox (Tangent)
2019-09-06 23:13:00NP的N是nondeterministic阿 不是Non-PNP problem can be solved by nondeterministic Turingmachine in polynomial time.
作者:
Aa841018 (andrew)
2019-09-06 23:29:00哦！謝謝兩位解惑！