作者LPH66 (-858993460)
看板CSSE
标题Re: [问题] halt problem 是无解还是NP-hard ?
时间Thu Oct 28 00:26:22 2010
※ 引述《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 却是要求要百分之百答对...
--
'You've sort of made up for it tonight,' said Harry. 'Getting the
sword. Finishing the Horcrux. Saving my life.'
'That makes me sound a lot cooler then I was,' Ron mumbled.
'Stuff like that always sounds cooler then it really was,' said
Harry. 'I've been trying to tell you that for years.'
-- Harry Potter and the Deathly Hollows, P.308
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.30.139
1F：→ ckey:先不管Win7的问题, 只要落在NP里不就是有解了?只是要用 10/29 09:32
2F：→ ckey:nondeterministic turing machine就可以在polynomial time解 10/29 09:32
3F：→ ckey:出~ 是我记错了吗? 怎麽和你说的不太一样? 10/29 09:33
4F：→ ckey:喔喔~ 我看成NPC了~ 10/29 09:34