作者sooge (喜欢平井桃)
看板Grad-ProbAsk
标题[理工] NP问题
时间Sun Jan 20 15:21:14 2019
小弟我有一个小小的NP问题希望有人可以解答一下
NP-hard的定义是：如果X是一个NP-hard的问题，则NP问题皆可以被polynomial time
的algo. reduce到X
NP-complete的定义：若X是NP-complete，则X属於NP也属於NP-hard
那我的疑问是
因为NP-hard是从NP reduction来的，一定有NP和NP-hard的性质
所以如果X是NP-hard的问题，那是不是就代表X一定是NP-complete的问题?
-----
Sent from JPTT on my HTC_D820u.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.82.69.160
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1547968883.A.A8C.html
※ 编辑: sooge (111.82.69.160), 01/20/2019 15:27:10
1F：推 eric131204: NP hard 不一定是NP吧 01/20 15:33
2F：→ z3588191: reduction不保证NP, 01/20 15:39
3F：→ sooge: 哦哦我懂了，刚刚忽然有奇怪的想法，谢谢楼上两位 01/20 15:49