作者s1020824 (HowardW)
看板Grad-ProbAsk
標題[理工] 演算法 np-hard 定義
時間Fri Oct 20 15:35:21 2017
大家午安
http://i.imgur.com/34XXXeQ.jpg
想請問一下
np-hard的定義是
"所有A屬於NP 且 A is polynomial-time reducible to B ,則B is np-hard"
那是否表示np-hard包含於np呢
如果不是的話
是表示說跟圖上一樣 np 跟 np-hard是兩個分開的集合嗎
這邊想不太通 請大大幫解析QQ
-----
Sent from JPTT on my HTC_M9u.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.250.52.154
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1508484926.A.2C4.html
推 can18: np-hard是至少跟np一樣難 可以想成難度>=np 10/20 15:56
→ can18: 但例如exponential 或 unsolved 也是np-hard 10/20 15:57
→ can18: 圖那樣是對的 10/20 15:58
→ s1020824: 所以是說np跟np-hard是兩個子集 10/20 16:16
→ s1020824: 有些問題只屬於np-hard而不屬於np嗎 10/20 16:16
推 krusnoopy: 有的 可以搜尋NP-hard but not NP-Complete 10/20 17:42
謝謝各位大大qq
※ 編輯: s1020824 (60.251.225.88), 10/20/2017 18:17:11