推 eric131204: NP hard 不一定是NP吧 01/20 15:33
→ z3588191: reduction不保證NP, 01/20 15:39
→ sooge: 哦哦我懂了，剛剛忽然有奇怪的想法，謝謝樓上兩位 01/20 15:49
小弟我有一個小小的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://www.ptt.cc/bbs/Grad-ProbAsk/M.1547968883.A.A8C.html
※ 編輯: sooge (111.82.69.160), 01/20/2019 15:27:10