作者ikjhyu (还没想到)
看板CSSE
标题请问NP-complete
时间Tue May 31 05:22:19 2005
如果一个问题是NP-complete
那可以证明这个问题不存在多项式时间解决的演算法吗?
记得P是否等於NP不是还没证明被证明吗?
但是演算法的宝典 "introduction to alogirhtms" THOMAS H. CORMEN
pp.990 上面Lemma34.5 再上面一点有一小段文字说..
(注:这一小节是在讲SAT问题)
text : "In fact, as has been claimed, there is strong evidence that no
polynomial time algorithm exists that solves the circuit satisfiability
problem because circuit satisfiability is NP-complete"
...疑惑..
盼高手解答..
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.59.211.123
※ 编辑: ikjhyu 来自: 61.59.211.123 (05/31 05:25)
※ 编辑: ikjhyu 来自: 61.59.211.123 (05/31 05:25)
1F：推 Hatred:他是说"strong evidence",没有说circuit SAT 140.112.30.113 05/31
2F：→ Hatred:没有polynomial time演算法:) 140.112.30.113 05/31
3F：推 Eventis:还没发现不等於没有啊XD 61.62.49.43 05/31
4F：→ Eventis:这个证明好像在做P != NP 61.62.49.43 05/31
5F：→ Eventis:不会比PNP简单到哪里去吧=.=" 61.62.49.43 05/31
6F：推 klain:没有polynomial-time演算法的问题充其量顶多可以 59.112.212.87 05/31
7F：→ klain:说这个问题不在P里面，但是不能说他是NP-complete 59.112.212.87 05/31
8F：→ klain:要证NP-complete就要照着定义走 59.112.212.87 05/31
9F：推 Eventis:0.0"...呃,原po问的东西不是这样. 61.62.49.43 05/31
10F：→ Eventis:他的已知是确定NPC........:) 61.62.49.43 05/31
11F：→ Eventis:但是NPC并不保证真的不存在solution in P吧? 61.62.49.43 05/31
12F：→ Eventis:NPC -> no solution in P <===....Orz... 61.62.49.43 05/31
13F：→ Eventis:这个能证出来的话就不需要费心证明PNP了啊XD 61.62.49.43 05/31
14F：→ Eventis:既然原po引用了ITA,那就看一下Thm34.4吧. 61.62.49.43 05/31
15F：→ Eventis:这个问题跟PNP是等价的啊0.0 61.62.49.43 05/31