※ 引述《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。