作者gcobs226484 (胖喵)
看板Grad-ProbAsk
标题[理工] 107中央资演17 105交大59
时间Sun Jan 26 10:46:34 2020
大家好 请问一下
https://i.imgur.com/oNhjUTY.jpg
不懂这个选项为什麽是True
X可以被所有NP reduce,代表X至少也有NP，所以Y是NP Hard成立吗？
https://i.imgur.com/2w1qk4F.jpg
再请看这题的C
错的原因是：NP Hard reduce的Y至少为NP Hard，但因没证明Y为NP，所以不保证其为NPC吗？
感觉观念有点问题，还请大家指教，感谢大家
-----
Sent from JPTT on my iPhone
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 39.9.163.226 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1580006796.A.06C.html
1F：推 Aa841018: 1.x reduce to y 01/26 10:58
2F：→ Aa841018: x is np hard，因为x不可能比y难，所以y至少也是np hard 01/26 10:58
3F：→ MASAGA: NP-hard不一定能在polynomial time reduce到NPC 01/26 12:02
4F：→ MASAGA: 除非你的NP-hard刚好也是NPC 01/26 12:02
5F：→ MASAGA: 你的叙述是对的 但跟这题错的原因有点不一样 01/26 12:03
6F：→ gcobs226484: 谢谢A大跟M大的解答 新年快乐 01/26 15:23