作者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://www.ptt.cc/bbs/Grad-ProbAsk/M.1580006796.A.06C.html
推 Aa841018: 1.x reduce to y 01/26 10:58
→ Aa841018: x is np hard，因為x不可能比y難，所以y至少也是np hard 01/26 10:58
→ MASAGA: NP-hard不一定能在polynomial time reduce到NPC 01/26 12:02
→ MASAGA: 除非你的NP-hard剛好也是NPC 01/26 12:02
→ MASAGA: 你的敘述是對的 但跟這題錯的原因有點不一樣 01/26 12:03
→ gcobs226484: 謝謝A大跟M大的解答 新年快樂 01/26 15:23