作者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