[理工] 107 成大程設(algo) ben4562002 PTT批踢踢實業坊

作者: ben4562002 (Bin) 2020-02-06 14:13:24

https://i.imgur.com/UPc6Iru.jpg
想請問一下，這題可以得出什麼結論呢？
我的想法是可以證明P=NP, 但不太會描述過程@@
煩請大大不吝指教ㄌ！

作者: ekids1234 (∵:☆星痕╭☆) 2020-02-06 14:25:00

所有 NP 可 reduce 到該 NPH-> 所有 NP = P -> P = NP = NPC

作者: ben4562002 (Bin) 2020-02-06 14:43:00

感謝～我有另個疑問如果是NPC有poly algo, 則也可以推得P=NP=NPC嗎?還是只能P=NP?

作者: ekids1234 (∵:☆星痕╭☆) 2020-02-06 15:38:00

可以NPH 包含 NPC，所以你提的只是這個說法的其中一個可能性而已

作者: ben4562002 (Bin) 2020-02-06 16:15:00

懂惹感謝解惑！

繼續閱讀