[理工] NP問題

看板Grad-ProbAsk作者sooge (喜歡平井桃)時間5年前 (2019/01/20 15:21)推噓1(1推 0噓 2→)

留言3則, 3人參與討論串2/3 (看更多)

小弟我有一個小小的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

推

eric131204

01/20 15:33, 5年前 , 1^F

01/20 15:33, 1^F

→

z3588191

01/20 15:39, 5年前 , 2^F

01/20 15:39, 2^F

→

sooge

01/20 15:49, 5年前 , 3^F

01/20 15:49, 3^F