......是我們系上的紅蟲學弟嗎 @@? ※ 引述《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)