[理工] 105交大資演 P與NP問題

看板Grad-ProbAsk作者 (exile)時間7年前 (2016/08/13 10:23), 編輯推噓2(2推 0噓 5→)
留言7則, 2人參與, 最新討論串1/1
http://imgur.com/a/UDiL4 交大105年資演第58(C)所說"as difficult as SAT"的SAT 是指n-SAT for n >= 3 嗎? 所以第58題答案為(D) ?? 然後阿 第59題的答案是B還是D呢? B==> NP 不就是non-derministic algorithm 可解 NP D==> factoring composite integer不就是NP嗎? (驗證答案的話，直接把答案成起來應該是polynomial time) 跪求大神求解~~XD -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.99.5 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1471054993.A.E91.html
推
08/13 12:14, , 1F
SAT 是指每一個 clause 內的 variable 數量沒有限制的問題
08/13 12:14, 1F
→
08/13 12:14, , 2F
2-SAT 是 P 可解
08/13 12:14, 2F
→
08/13 12:16, , 3F
Integer factorization 是 NP 所以 59 D 是對的
08/13 12:16, 3F
→
08/13 12:16, , 4F
59 B 是錯在 verification 需要 certificate
08/13 12:16, 4F
→
08/13 12:26, , 5F
NP 不就是non-derministic algorithm 可解 NP嗎?
08/13 12:26, 5F
→
08/13 12:27, , 6F
為什麼還會需要做certificate(證明)?
08/13 12:27, 6F
推
08/14 04:11, , 7F
NP 的另一個定義方式就是用 verification
08/14 04:11, 7F
‣ 更多 exilelast 的文章
文章代碼(AID): #1NheIHwH (Grad-ProbAsk)