楼主:
Aa841018 (andrew)
2019-09-01 15:11:46https://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:00NPC一定存在...图同构问题，Hamilton，3SAT都是啊
楼主:
Aa841018 (andrew)
2019-09-02 18:05:00可是虽然所有np都可reduce到npc，但没人保证npc一定可以被解决啊！
作者:
mistel (Mistel)
2019-09-02 18:24:00NPC蒐集的不是不能被解决的问题，而是认为没有多项式时间解法的问题，因为一定都有暴力解存在，而且NPC其实是NP跟NP-Hard的交集
作者:
firejox (Tangent)
2019-09-06 23:13:00NP的N是nondeterministic阿 不是Non-PNP problem can be solved by nondeterministic Turingmachine in polynomial time.
楼主:
Aa841018 (andrew)
2019-09-06 23:29:00哦！谢谢两位解惑！