請問NP-complete

[ikjhyu (還沒想到)]

如果一個問題是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)
推 Hatred:他是說"strong evidence",沒有說circuit SAT
→ Hatred:沒有polynomial time演算法:)
推 Eventis:還沒發現不等於沒有啊XD
→ Eventis:這個證明好像在做P != NP
→ Eventis:不會比PNP簡單到哪裡去吧=.="
推 klain:沒有polynomial-time演算法的問題充其量頂多可以
→ klain:說這個問題不在P裡面，但是不能說他是NP-complete
→ klain:要証NP-complete就要照著定義走
推 Eventis:0.0"...呃,原po問的東西不是這樣.
→ Eventis:他的已知是確定NPC........:)
→ Eventis:但是NPC並不保證真的不存在solution in P吧?
→ Eventis:NPC -> no solution in P <===....Orz...
→ Eventis:這個能證出來的話就不需要費心證明PNP了啊XD
→ Eventis:既然原po引用了ITA,那就看一下Thm34.4吧.
→ Eventis:這個問題跟PNP是等價的啊0.0