[理工] 演算法257！（NP)

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