1. PTT
  2. Grad-ProbAsk

[理工] NP問題觀念

作者: fmtshk (fmtshk)   2020-10-31 18:46:08
https://i.imgur.com/HlaNTvI.jpg
大家好
請問這題的P1可以reduced到P2，代表解P1不會比P2難
然後P1是NP-Complete所以它也是NP-hard，這代表P2也是NP-hard。
那P2應該也能reduced到P1?
這樣想對嗎？
作者: jimmylin1024 (wiseman)   2020-11-01 09:30:00
P1 can be reduce to P2 的意思是P2的難度大於等於P1，而P1 是NP complete 代表P2在NP Hard ，但是我們不知道P2是不是屬於NP ，所以不能確定P2是NP complete所以我覺得P2不行被Reduce to P1
作者: fmtshk (fmtshk)   2020-11-01 17:42:00
原來如此，感謝回答
繼續閱讀
[理工] vertex cover reduction to HCff00662299[理工] 台大工科 linked listjoywilliamjo[理工] 01大背包問題_列表fmtshk[理工] peak finding 演算法fmtshk[理工] 97 成大計系lanlansaysay[理工] 線代 p7-130 67題sevfouyu11[理工] OS 98交大資聯(software interruptdogdogh[線代] 109台大資工 線代第九題onemore9Re: [理工] 108交大計系5kyuudonut[理工] 演算法 Big O相關問題kaemu1006

Links booklink

Contact Us: admin [ a t ] ucptt.com