※ 引述《Aa841018 (andrew)》之铭言： : https://i.imgur.com/oiFkCVm.jpg : https://i.imgur.com/G23Xg6H.jpg : (c):这和笔记好像有点矛盾，NPC不应该存在P的解法，否则NP=P : 但NPC的某些input 又可以在非exponential time解开 : 时间复杂度排序：exponential>polynomial : （=n^k) : 那如果不在exponential 解开，那肯定在polynomial范围内，这岂不是和笔记内容矛盾? : 不知道哪里出错… 因为题目中有说 for all kinds of input，但是实际上无论 P 等不等 於 NP，一个 NPC 问题可能有存在特例，使得该类 input 可以很快的解 出来。像是 SAT 是 NPC ，但是 2-SAT 却是 P。 如果题目把 for all kinds of input 换成 in worst case，也还是不 对，因为到目前为止我们没办法排除 P = NP 的可能，如果 P = NP 的 话，那所有 NPC 的问题的所有输入都可以在 P 中解。 如果题目把 for all kinds of input 换成 in worst case 且又假设 P != NP，还是不对，因为 P != NP，不代表 NPC 不能在 subexponential time 解，有兴趣的可以看看 exponential time hypothesis。 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 73.202.90.47 (美国) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1579667031.A.039.html