https://i.imgur.com/oiFkCVm.jpg
https://i.imgur.com/G23Xg6H.jpg
想问(b)(c)
(b):这题详解是不是少了假设x=np?因为没有这假设,就算sat(npc) reduce to X,x也不
见得是npc说不定是np hard
(c):这和笔记好像有点矛盾,NPC不应该存在P的解法,否则NP=P
但NPC的某些input 又可以在非exponential time解开
时间复杂度排序:exponential>polynomial
(=n^k)
那如果不在exponential 解开,那肯定在polynomial范围内,这岂不是和笔记内容矛盾?
不知道哪里出错…