所有属於P,NP,NP-Hard,NP-Complete的问题， 就是turing machine decidable problem， 反之则属non-decidable problem。 学长告诉我第二句是错的,他说因为NP-Hard之中包含有undecidable problem。 halting problem属於NP-Hard, 而且turing machine undecidable. 这算是一个学长所说的例子吗? 所以请问我学长说的是对的吗? 另外若我学长说的是正确的, 那麽我可以说所有的P及NP都属於turing machine decidable? NP-Hard有部分属於decidable,另一部分属於undecidable? 那麽究竟是undicidable包含NP-Hard,还是NP-Hard包含undecidable? 请版上前辈指正. 谢谢.. -- 朱色虫居: http://city.udn.com/v1/blog/photo/index.jsp?uid=l314　(人文) http://tw.myblog.yahoo.com/l314kimo (资讯) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.119.201.20 ※ 编辑: l314 来自: 140.119.201.20 (01/28 23:11)