推 Aa841018: 哦！謝謝講解，最後一個假設如果考出來我十之八九會錯 01/22 20:02
推 zaqxsw2230: 推 01/24 14:13
※ 引述《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://www.ptt.cc/bbs/Grad-ProbAsk/M.1579667031.A.039.html