[理工] NP問題觀念

[fmtshk (fmtshk)]

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
推 jimmylin1024: P1 can be reduce to P2 的意思是P2的難度大於等於P
→ jimmylin1024: 1，而P1 是NP complete 代表P2在NP Hard ，但是我們
→ jimmylin1024: 不知道P2是不是屬於NP ，所以不能確定P2是NP comple
→ jimmylin1024: te
→ jimmylin1024: 所以我覺得P2不行被Reduce to P1
→ fmtshk: 原來如此，感謝回答