※ 引述《LFking (小均)》之銘言：
: 最近小弟在找當機問題(halting problem)的相關資料時
: 大多數都是用圖靈機反證得知能夠判斷halt的程式不存在(無解
: 但卻也有人說當機問題是NP-hard ?
: http://en.wikipedia.org/wiki/NP-hard
: by the way,
: 那又Windows 7為何可以判斷一個程式"可能"已經當機?
NP-hard 和 undecidability 並不衝突啊...
一個問題 H 是 NP-hard 只有要求
所有 NP 問題 (或者等價地, 存在某一 NP-complete 問題)可以 reduce 到 H
並沒有要求 H 要在 NP 當中
(有要求的話它就是 NP-complete)
也就是說一個問題是 NP-hard 只代表它至少和 NP 裡最難的那些問題一樣難
概念上這有點下界的感覺 而上界卻是開放的...
這樣的 H 當然可以是 undecidable 的問題
因為 reduce 到 X 的意思是若有一個能夠解 X 的黑盒子則我們能解別的東西
這 X 可沒說是怎麼解的...
至於你說的 Win 7 的問題
這可以有很多猜測的方法 因為如你所說它所判斷的是這程式「可能」已經當機
也就是它不一定要百分之百準
而 halting problem 卻是要求要百分之百答對...