Re: [問題] halt problem 是無解還是NP-hard ?
※ 引述《LFking (小均)》之銘言：
: 感謝大大的回答,
: 但NP-hard是否也包含 無解的問題 ？
: 所謂的NP不就是 有解的題目 但要花很多時間（指數時間）？
是的
NP-hard 雖然叫這個名字 但它並不是 NP 的子集
維基上的圖應該很清楚的表示了這一點:
http://en.wikipedia.org/wiki/NP-hard
http://en.wikipedia.org/wiki/File:P_np_np-complete_np-hard.svg
你可能是把 NP-hard 和 NP-complete 弄混了
NP-complete 才是 NP 的子集 它正是 NP-hard 和 NP 的交集
--
"LPH" is for "Let Program Heal us"....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.28.92
推
11/06 20:31, , 1F
11/06 20:31, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 4 之 4 篇)：