[理工] 算法257！（NP) Aa841018 PTT批踢踢实业坊

楼主: Aa841018 (andrew) 2019-09-01 15:11:46

https://i.imgur.com/tu5Vo8A.jpg
请问2.（2）（106交大）
题目：A是NP则必定存在一个NP algo B可解A
这题为什么是T啊？

作者: JKLee (J.K.Lee) 2019-09-01 16:28:00

因为NPC的存在

作者: mistel (Mistel) 2019-09-01 18:07:00

楼上说的是指所有NP都可以归约到NPC的意思吗？

楼主: Aa841018 (andrew) 2019-09-01 18:15:00

可是题目没特别说NPC存在……

作者: mistel (Mistel) 2019-09-01 18:47:00

NPC一定存在...图同构问题，Hamilton，3SAT都是啊

楼主: Aa841018 (andrew) 2019-09-02 18:05:00

可是虽然所有np都可reduce到npc，但没人保证npc一定可以被解决啊！

作者: mistel (Mistel) 2019-09-02 18:24:00

NPC蒐集的不是不能被解决的问题，而是认为没有多项式时间解法的问题，因为一定都有暴力解存在，而且NPC其实是NP跟NP-Hard的交集

作者: firejox (Tangent) 2019-09-06 23:13:00

NP的N是nondeterministic阿不是Non-PNP problem can be solved by nondeterministic Turingmachine in polynomial time.

楼主: Aa841018 (andrew) 2019-09-06 23:29:00

哦！谢谢两位解惑！

继续阅读