[理工] 算法 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