作者LFking (小均)
看板CSSE
標題Re: [問題] halt problem 是無解還是NP-hard ?
時間Mon Nov 1 12:15:05 2010
感謝大大的回答,
但NP-hard是否也包含 無解的問題 ？
所謂的NP不就是 有解的題目 但要花很多時間（指數時間）？
※ 引述《LPH66 (-858993460)》之銘言：
: ※ 引述《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 卻是要求要百分之百答對...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.133.13.43
1F：推 iamnumbea1:我記得NP的定義不是給定一個解 可以在多項式時間內 11/01 15:49
2F：→ iamnumbea1:驗證是否為其解嗎 11/01 15:49