作者fmtshk (fmtshk)
看板Grad-ProbAsk
标题[理工] NP问题观念
时间Sat Oct 31 18:46:08 2020
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1604141170.A.6DD.html
1F：推 jimmylin1024: P1 can be reduce to P2 的意思是P2的难度大於等於P 11/01 09:30
2F：→ jimmylin1024: 1，而P1 是NP complete 代表P2在NP Hard ，但是我们 11/01 09:30
3F：→ jimmylin1024: 不知道P2是不是属於NP ，所以不能确定P2是NP comple 11/01 09:30
4F：→ jimmylin1024: te 11/01 09:30
5F：→ jimmylin1024: 所以我觉得P2不行被Reduce to P1 11/01 09:32
6F：→ fmtshk: 原来如此，感谢回答 11/01 17:42