[理工] 演算法257！（NP) Aa841018 PTT批踢踢實業坊

作者: Aa841018 (andrew) 2019-09-01 15:11:46

https://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:00

NPC一定存在...圖同構問題，Hamilton，3SAT都是啊

作者: Aa841018 (andrew) 2019-09-02 18:05:00

可是雖然所有np都可reduce到npc，但沒人保證npc一定可以被解決啊！

作者: mistel (Mistel) 2019-09-02 18:24:00

NPC蒐集的不是不能被解決的問題，而是認為沒有多項式時間解法的問題，因為一定都有暴力解存在，而且NPC其實是NP跟NP-Hard的交集

作者: firejox (Tangent) 2019-09-06 23:13:00

NP的N是nondeterministic阿不是Non-PNP problem can be solved by nondeterministic Turingmachine in polynomial time.

作者: Aa841018 (andrew) 2019-09-06 23:29:00

哦！謝謝兩位解惑！

繼續閱讀