看板 [ CSSE ]
討論串[問題] halt problem 是無解還是NP-hard ?
共 4 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] halt problem 是無解還是NP-hard ?
推噓0(0推 0噓 4→)留言4則，0人參與, 最新作者LFking (小均)時間14年前 (2010/10/27 23:25), 編輯資訊
1
0
1
內容預覽:
最近小弟在找當機問題(halting problem)的相關資料時. 大多數都是用圖靈機反證得知能夠判斷halt的程式不存在(無解. 但卻也有人說當機問題是NP-hard ?. http://en.wikipedia.org/wiki/NP-hard. by the way,. 那又Windows
#2
Re: [問題] halt problem 是無解還是NP-hard ?
推噓0(0推 0噓 4→)留言4則，0人參與, 最新作者LPH66 (-858993460)時間14年前 (2010/10/28 00:26), 編輯資訊
1
0
1
內容預覽:
NP-hard 和 undecidability 並不衝突啊.... 一個問題 H 是 NP-hard 只有要求. 所有 NP 問題 (或者等價地, 存在某一 NP-complete 問題)可以 reduce 到 H. 並沒有要求 H 要在 NP 當中. (有要求的話它就是 NP-complete)
(還有540個字)
#3
Re: [問題] halt problem 是無解還是NP-hard ?
推噓1(1推 0噓 1→)留言2則，0人參與, 最新作者LFking (小均)時間14年前 (2010/11/01 12:15), 編輯資訊
1
0
1
內容預覽:
感謝大大的回答,. 但NP-hard是否也包含 無解的問題 ？. 所謂的NP不就是 有解的題目 但要花很多時間（指數時間）？. --. ※ 發信站: 批踢踢實業坊(ptt.cc). ◆ From: 140.133.13.43.
#4
Re: [問題] halt problem 是無解還是NP-hard ?
推噓1(1推 0噓 0→)留言1則，0人參與, 最新作者LPH66 (-858993460)時間14年前 (2010/11/01 16:02), 編輯資訊
0
0
2
內容預覽:
是的. NP-hard 雖然叫這個名字 但它並不是 NP 的子集. 維基上的圖應該很清楚的表示了這一點:. http://en.wikipedia.org/wiki/NP-hard. http://en.wikipedia.org/wiki/File:P_np_np-complete_np-hard
(還有26個字)
首頁
上一頁
1
下一頁
尾頁