看板 [ Grad-ProbAsk ]
討論串[理工] 105清大（P&NP)!
共 2 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[理工] 105清大（P&NP)!
推噓2(2推 0噓 18→)留言20則，0人參與, 4年前最新作者Aa841018 (andrew)時間4年前 (2020/01/21 20:33), 編輯資訊
1
2
0
內容預覽:
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. (
(還有139個字)
#2
Re: [理工] 105清大（P&NP)!
推噓2(2推 0噓 0→)留言2則，0人參與, 4年前最新作者FRAXIS (喔喔)時間4年前 (2020/01/22 12:23), 編輯資訊
0
2
0
內容預覽:
因為題目中有說 for all kinds of input，但是實際上無論 P 等不等. 於 NP，一個 NPC 問題可能有存在特例，使得該類 input 可以很快的解. 出來。像是 SAT 是 NPC ，但是 2-SAT 卻是 P。. 如果題目把 for all kinds of input 換
(還有207個字)
首頁
上一頁
1
下一頁
尾頁