推 l314:喔~~喔~~謝謝學長~~~ ^^ 01/29 14:10
......是我們系上的紅蟲學弟嗎 @@?
※ 引述《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)