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

SAT 是指每一個 clause 內的 variable 數量沒有限制的問題2-SAT 是 P 可解Integer factorization 是 NP 所以 59 D 是對的59 B 是錯在 verification 需要 certificate

NP 不就是non-derministic algorithm 可解 NP嗎?為什麼還會需要做certificate(證明)?

NP 的另一個定義方式就是用 verification