※ 引述《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 却是要求要百分之百答对...