......是我们系上的红虫学弟吗 @@? ※ 引述《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)