[理工] 107中央資演17 105交大59

看板Grad-ProbAsk作者 (胖喵)時間5年前 (2020/01/26 10:46), 編輯推噓1(1推 0噓 5→)
留言6則, 3人參與, 5年前最新討論串1/1
大家好 請問一下 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
推
01/26 10:58, 5年前 , 1F
1.x reduce to y
01/26 10:58, 1F
→
01/26 10:58, 5年前 , 2F
x is np hard，因為x不可能比y難，所以y至少也是np hard
01/26 10:58, 2F
→
01/26 12:02, 5年前 , 3F
NP-hard不一定能在polynomial time reduce到NPC
01/26 12:02, 3F
→
01/26 12:02, 5年前 , 4F
除非你的NP-hard剛好也是NPC
01/26 12:02, 4F
→
01/26 12:03, 5年前 , 5F
你的敘述是對的 但跟這題錯的原因有點不一樣
01/26 12:03, 5F
→
01/26 15:23, 5年前 , 6F
謝謝A大跟M大的解答 新年快樂
01/26 15:23, 6F
‣ 更多 gcobs226484 的文章
文章代碼(AID): #1UBFsC1i (Grad-ProbAsk)