作者ykjiang (Yukuan)
看板CSSE
標題Re: 請問NP-complete
時間Wed Jun 1 01:04:57 2005
※ 引述《ikjhyu (還沒想到)》之銘言：
: 如果一個問題是NP-complete
: 那可以證明這個問題不存在多項式時間解決的演算法嗎?
^^^^^^^^^^^^^^^^^^^^^^
polynomial time DETERMINISTIC algorithm 比較完整，雖然常省略。
不行。
: 記得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"
: ...疑惑..
: 盼高手解答..
The strong evidence means the "NPC satifiable". :)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.70.103.119
※ 編輯: ykjiang 來自: 203.70.103.119 (06/01 01:06)