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