[理工] 演算法 np-hard 定義

看板Grad-ProbAsk作者 (HowardW)時間8年前 (2017/10/20 15:35), 8年前編輯推噓2(2推 0噓 4→)
留言6則, 3人參與, 8年前最新討論串1/1
大家午安 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
推
10/20 15:56, 8年前 , 1F
np-hard是至少跟np一樣難 可以想成難度>=np
10/20 15:56, 1F
→
10/20 15:57, 8年前 , 2F
但例如exponential 或 unsolved 也是np-hard
10/20 15:57, 2F
→
10/20 15:58, 8年前 , 3F
圖那樣是對的
10/20 15:58, 3F
→
10/20 16:16, 8年前 , 4F
所以是說np跟np-hard是兩個子集
10/20 16:16, 4F
→
10/20 16:16, 8年前 , 5F
有些問題只屬於np-hard而不屬於np嗎
10/20 16:16, 5F
推
10/20 17:42, 8年前 , 6F
有的 可以搜尋NP-hard but not NP-Complete
10/20 17:42, 6F
謝謝各位大大qq ※ 編輯: s1020824 (60.251.225.88), 10/20/2017 18:17:11
‣ 更多 s1020824 的文章
文章代碼(AID): #1PwQS-B4 (Grad-ProbAsk)