[理工] 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