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