[理工] 107 成大程設(algo)

看板Grad-ProbAsk作者 (Bin)時間4年前 (2020/02/06 14:13), 編輯推噓1(1推 0噓 9→)
留言10則, 2人參與, 4年前最新討論串1/1
https://i.imgur.com/UPc6Iru.jpg
想請問一下，這題可以得出什麼結論呢？ 我的想法是可以證明P=NP, 但不太會描述過程@@ 煩請大大不吝指教ㄌ！ ---- Sent from BePTT on my Sony G8142 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.77.205.158 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1580969606.A.978.html
推
02/06 14:25, 4年前 , 1F
所有 NP 可 reduce 到該 NPH
02/06 14:25, 1F
→
02/06 14:25, 4年前 , 2F
-> 所有 NP = P -> P = NP = NPC
02/06 14:25, 2F
→
02/06 14:43, 4年前 , 3F
感謝～
02/06 14:43, 3F
→
02/06 14:45, 4年前 , 4F
我有另個疑問
02/06 14:45, 4F
→
02/06 14:45, 4年前 , 5F
如果是NPC有poly algo, 則也可以推得P=NP=NPC嗎?
02/06 14:45, 5F
→
02/06 14:45, 4年前 , 6F
還是只能P=NP?
02/06 14:45, 6F
→
02/06 15:38, 4年前 , 7F
可以
02/06 15:38, 7F
→
02/06 15:39, 4年前 , 8F
NPH 包含 NPC，所以你提的只是這個說法的其中一個可能
02/06 15:39, 8F
→
02/06 15:39, 4年前 , 9F
性而已
02/06 15:39, 9F
→
02/06 16:15, 4年前 , 10F
懂惹 感謝解惑！
02/06 16:15, 10F
‣ 更多 ben4562002 的文章
文章代碼(AID): #1UEww6bu (Grad-ProbAsk)