[问题] halt problem 是无解还是NP-hard ? LFking PTT批踢踢实业坊

[问题] halt problem 是无解还是NP-hard ?

楼主: LFking (小均) 2010-10-27 23:25:21

最近小弟在找当机问题(halting problem)的相关资料时
大多数都是用图灵机反证得知能够判断halt的程式不存在(无解
但却也有人说当机问题是NP-hard ?
http://en.wikipedia.org/wiki/NP-hard
by the way,
那又Windows 7为何可以判断一个程式"可能"已经当机?

作者: eva19452002 (^^) 0000-00-00 00:00:00

有些程式在执行量运算，windows会判断已当机，但是过一段时间，等运算结束后，就好了上面应该打大量运算才对，不是量运算

楼主: LFking (小均) 2009-01-01 18:47:00

thanks!!

继续阅读

[情报] 2010 资讯安全技术研讨会lizard0619 Re: [问题] SQL count 的替代方法cspy [问题] 关于物件导向分析问题yungshiang [请益] 微核心(microkernel)是不是真的比较好?jokker Re: [问题] 几题BigO证明还有观念疑问micklin [问题] 几题BigO证明还有观念疑问Lizstlin Re: [问题] SQL count 的替代方法yauhh Re: [问题] SQL count 的替代方法neversay Re: [问题] SQL count 的替代方法dayyoung [问题] SQL count 的替代方法dayyoung