PTT
Submit
Submit
选择语言
正體中文
简体中文
PTT
Grad-ProbAsk
[理工] 105交大资演 P与NP问题
楼主:
exilelast
(exile)
2016-08-13 10:23:11
交大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
作者:
FRAXIS
(喔喔)
2016-08-13 12:14:00
SAT 是指每一个 clause 内的 variable 数量没有限制的问题2-SAT 是 P 可解Integer factorization 是 NP 所以 59 D 是对的59 B 是错在 verification 需要 certificate
楼主:
exilelast
(exile)
2016-08-13 12:26:00
NP 不就是non-derministic algorithm 可解 NP吗?为什么还会需要做certificate(证明)?
作者:
FRAXIS
(喔喔)
2016-08-14 04:11:00
NP 的另一个定义方式就是用 verification
继续阅读
[理工] 离散 命题逻辑
yorunohoshi
[理工] 计组 第一章
brad84622
[理工] [线代] 向量空间
kyuudonut
[理工] 离散 图论 定义
hopward
Re: [理工] 离散 图论
gary19941208
[理工] 电晶体输出特性曲线
LimitDown
[理工] 离散 图论
tomdog12345
帮忙判断电磁学考题难度
superdevil
[理工] 离散数学第六章ismorphic
Gene0515
[理工] 离散 群 络
yorunohoshi
Links
booklink
Contact Us: admin [ a t ] ucptt.com