[理工] 107中央資演17 105交大59 gcobs226484 PTT批踢踢實業坊

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

作者: gcobs226484 (胖喵) 2020-01-26 10:46:34

大家好請問一下
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嗎？
感覺觀念有點問題，還請大家指教，感謝大家

作者: Aa841018 (andrew) 2020-01-26 10:58:00

1.x reduce to yx is np hard，因為x不可能比y難，所以y至少也是np hard

作者: MASAGA (和泉千晶我老婆) 2020-01-26 12:02:00

NP-hard不一定能在polynomial time reduce到NPC除非你的NP-hard剛好也是NPC你的敘述是對的但跟這題錯的原因有點不一樣

作者: gcobs226484 (胖喵) 2020-01-26 15:23:00

謝謝A大跟M大的解答新年快樂

繼續閱讀

[理工] 計組下 53 & 58lucy35 [理工] 中央103計系ponwar87123 102清大計系chiuchang [理工] 103中央資演兩題ponwar87123 [理工] 08電機丙離散bochengchen [理工] 103中央離散必要但不充分ponwar87123 [理工] Reduction 107 清大計科 8DLHZ 線代微積分！eric17195 102清大計系chiuchang [理工] 計組_關於CPIfmtshk