作者Aa841018 (andrew)
看板Grad-ProbAsk
標題[理工] 演算法257！（NP)
時間Sun Sep 1 15:11:46 2019
https://i.imgur.com/tu5Vo8A.jpg
請問2.（2） （106交大）
題目：A是NP則必定存在一個NP algo B可解A
這題為什麼是T啊？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.13.99.77 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1567321908.A.992.html
1F：→ JKLee: 因為NPC的存在 09/01 16:28
2F：推 mistel: 樓上說的是指所有NP都可以歸約到NPC的意思嗎？ 09/01 18:07
3F：→ Aa841018: 可是題目沒特別說NPC存在…… 09/01 18:15
4F：推 mistel: NPC一定存在...圖同構問題，Hamilton，3SAT都是啊 09/01 18:47
5F：→ Aa841018: 可是雖然所有np都可reduce到npc，但沒人保證npc一定可以 09/02 18:05
6F：→ Aa841018: 被解決啊！ 09/02 18:05
7F：推 mistel: NPC蒐集的不是不能被解決的問題，而是認為沒有多項式時間 09/02 18:24
8F：→ mistel: 解法的問題，因為一定都有暴力解存在，而且NPC其實是NP跟 09/02 18:24
9F：→ mistel: NP-Hard的交集 09/02 18:24
10F：→ firejox: NP的N是nondeterministic阿 不是Non-P 09/06 23:13
11F：→ firejox: NP problem can be solved by nondeterministic Turing 09/06 23:16
12F：→ firejox: machine in polynomial time. 09/06 23:17
13F：→ Aa841018: 哦！謝謝兩位解惑！ 09/06 23:29