[理工] 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

懂惹感谢解惑！

继续阅读