請問NP-complete
如果一個問題是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)
推
140.112.30.113 05/31, , 1F
140.112.30.113 05/31, 1F
→
140.112.30.113 05/31, , 2F
140.112.30.113 05/31, 2F
推
61.62.49.43 05/31, , 3F
61.62.49.43 05/31, 3F
→
61.62.49.43 05/31, , 4F
61.62.49.43 05/31, 4F
→
61.62.49.43 05/31, , 5F
61.62.49.43 05/31, 5F
推
59.112.212.87 05/31, , 6F
59.112.212.87 05/31, 6F
→
59.112.212.87 05/31, , 7F
59.112.212.87 05/31, 7F
→
59.112.212.87 05/31, , 8F
59.112.212.87 05/31, 8F
推
61.62.49.43 05/31, , 9F
61.62.49.43 05/31, 9F
→
61.62.49.43 05/31, , 10F
61.62.49.43 05/31, 10F
→
61.62.49.43 05/31, , 11F
61.62.49.43 05/31, 11F
→
61.62.49.43 05/31, , 12F
61.62.49.43 05/31, 12F
→
61.62.49.43 05/31, , 13F
61.62.49.43 05/31, 13F
→
61.62.49.43 05/31, , 14F
61.62.49.43 05/31, 14F
→
61.62.49.43 05/31, , 15F
61.62.49.43 05/31, 15F
討論串 (同標題文章)
CSSE 近期熱門文章
PTT數位生活區 即時熱門文章
