[理工] 演算法 np-hard 定義 s1020824 PTT批踢踢實業坊

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

作者: s1020824 (HowardW) 2017-10-20 15:35:21

大家午安
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

作者: can18 (18號) 2017-10-20 15:56:00

np-hard是至少跟np一樣難可以想成難度>=np但例如exponential 或 unsolved 也是np-hard圖那樣是對的

作者: s1020824 (HowardW) 2017-10-20 16:16:00

所以是說np跟np-hard是兩個子集有些問題只屬於np-hard而不屬於np嗎

作者: krusnoopy (push) 2017-10-20 17:42:00

有的可以搜尋NP-hard but not NP-Complete

繼續閱讀

[理工請益] wayne418418 [理工] 計組p459lovepipi Re: [理工] OS fork( )題目JKLee [理工] OS fork( )題目WachinMs [理工] 徵求Principles of Communication 7th byb0241091 [理工] 機械製造wayne418418 [理工] 演算法 Master Theorem 的常數範圍JKLee 線代 102台大工科fatezero5262 [理工] 計組上冊 p.551 第30題bobsonlin [理工] 徵Fundamental of logic design 7th by Rb0241091