作者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