→ JKLee: 因為NPC的存在 09/01 16:28
推 mistel: 樓上說的是指所有NP都可以歸約到NPC的意思嗎？ 09/01 18:07
→ Aa841018: 可是題目沒特別說NPC存在…… 09/01 18:15
推 mistel: NPC一定存在...圖同構問題，Hamilton，3SAT都是啊 09/01 18:47
→ Aa841018: 可是雖然所有np都可reduce到npc，但沒人保證npc一定可以 09/02 18:05
→ Aa841018: 被解決啊！ 09/02 18:05
推 mistel: NPC蒐集的不是不能被解決的問題，而是認為沒有多項式時間 09/02 18:24
→ mistel: 解法的問題，因為一定都有暴力解存在，而且NPC其實是NP跟 09/02 18:24
→ mistel: NP-Hard的交集 09/02 18:24
→ firejox: NP的N是nondeterministic阿 不是Non-P 09/06 23:13
→ firejox: NP problem can be solved by nondeterministic Turing 09/06 23:16
→ firejox: machine in polynomial time. 09/06 23:17
→ Aa841018: 哦！謝謝兩位解惑！ 09/06 23:29