作者haniwang (hani)
看板Grad-ProbAsk
标题[理工] NP
时间Mon Feb 11 08:21:41 2019
If an NP-complete problem can be solved deterministically in O(n^3),then every
problem in NP can be solved in O(n^3).
If a problem that is in the class NP has a polynomial time solution,then P=NP.
请问上面这两个叙述对吗？
麻烦各位了！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 223.139.0.113
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1549844504.A.72F.html
1F：推 feveral: True false 02/11 09:00
2F：推 TEPLUN: 都错 02/11 09:08
3F：→ GeniusPuddin: 我听课的理解是只要能多项式时间内互推就是一样难? 02/11 09:08
4F：→ GeniusPuddin: 所以某个NPC可以n^3应该不保证其它也n^3内0.0? 求解 02/11 09:08
5F：→ GeniusPuddin: 2的话是不是要NPC才有保证 02/11 09:10
6F：推 zaq851017: 1. True 2. False 02/11 09:53
7F：推 zaq851017: 1.的话因为是NPC 所以所有NP可以reduce到它 所以它 02/11 09:55
8F：→ zaq851017: 上界是O(n^3)也保证其他NP ~~ 02/11 09:55
9F：→ zaq851017: 一个A 可以 reduce到 B B如果可以O(n^3)也可以保证A 02/11 09:56
10F：推 nannnnn: a也错吧，reduce过去也要时间不是吗?如果reduce要n^4转换 02/11 09:59
11F：→ nannnnn: 时间，那不就没办法在n^3内解了 02/11 09:59
12F：推 zaq851017: 对齁没考虑到这个XD 应该是楼上说得这样 02/11 10:03
13F：推 ekids1234: 对 2 要 NPC NP不够 顶多把该问题从NP踢出去 02/11 10:20