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