[理工] NP問題觀念

看板Grad-ProbAsk作者 (fmtshk)時間5年前 (2020/10/31 18:46), 編輯推噓1(1推 0噓 5→)
留言6則, 2人參與, 5年前最新討論串1/1
https://i.imgur.com/HlaNTvI.jpg
大家好 請問這題的P1可以reduced到P2，代表解P1不會比P2難 然後P1是NP-Complete所以它也是NP-hard，這代表P2也是NP-hard。 那P2應該也能reduced到P1? 這樣想對嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.50.188.2 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1604141170.A.6DD.html
推
11/01 09:30, 5年前 , 1F
P1 can be reduce to P2 的意思是P2的難度大於等於P
11/01 09:30, 1F
→
11/01 09:30, 5年前 , 2F
1，而P1 是NP complete 代表P2在NP Hard ，但是我們
11/01 09:30, 2F
→
11/01 09:30, 5年前 , 3F
不知道P2是不是屬於NP ，所以不能確定P2是NP comple
11/01 09:30, 3F
→
11/01 09:30, 5年前 , 4F
te
11/01 09:30, 4F
→
11/01 09:32, 5年前 , 5F
所以我覺得P2不行被Reduce to P1
11/01 09:32, 5F
→
11/01 17:42, 5年前 , 6F
原來如此，感謝回答
11/01 17:42, 6F
‣ 更多 fmtshk 的文章
文章代碼(AID): #1VdK1oRT (Grad-ProbAsk)