作者neversay (子不语)
看板CSSE
标题Re: [问题] 请问NP-completeness
时间Mon Jan 29 01:12:56 2007
......是我们系上的红虫学弟吗 @@?
※ 引述《l314 (红虫)》之铭言:
: 所有属於P,NP,NP-Hard,NP-Complete的问题,
P:可在多项式时间
解决与
验证的问题
NP:可在多项式时间
验证的问题
NP-Hard:所有NP问题都可变换(reduce)成的问题
NP-Complete:既是NP又是NP-Hard的问题
: 就是turing machine decidable problem,
: 反之则属non-decidable problem。
: 学长告诉我第二句是错的,他说因为NP-Hard之中包含有undecidable problem。
: halting problem属於NP-Hard,
没错,halting problem是一个undecidable decision problem
(不可决定的 决定性问题),详情可看wikipeida对NP-Hard
#examples的举例。
: 而且turing machine undecidable.
: 这算是一个学长所说的例子吗?
: 所以请问我学长说的是对的吗?
是对的呀。
: 另外若我学长说的是正确的,
: 那麽我可以说所有的P及NP都属於turing machine decidable?
yes
decidable problem是说这些问题有「可在有限时间内算出答案的演算法」
所以,decidable/undecidable指的是这个问题有没有可用於有限时间求解的演算法
decision/function problem指的是问题输出的性质,跟有无适当演算法无关。
: NP-Hard有部分属於decidable,另一部分属於undecidable?
yes, for instance:
SAT问题是NP-Hard且decidable (因为SAT是NP-complete问题)
Halting problem 是NP-Hard且undecidable
: 那麽究竟是undicidable包含NP-Hard,还是NP-Hard包含undecidable?
: 请版上前辈指正.
: 谢谢..
他们没有互相包含,顶多是有交集。
--
逝去的爱,使生命更丰富。
LIFE has become richer by the love that has been lost.
--泰戈尔,漂鸟集.223。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.135.21.8
※ 编辑: neversay 来自: 220.135.21.8 (01/29 01:14)
1F:推 l314:喔~~喔~~谢谢学长~~~ ^^ 01/29 14:10