[問題] 請問NP-completeness
所有屬於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)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
CSSE 近期熱門文章
PTT數位生活區 即時熱門文章
