[理工] 算法 AgentSkye56 PTT批踢踢实业坊

[理工] 算法

楼主: AgentSkye56 (大安周渝民) 2014-11-18 00:18:56

名校上的一题
If an NP-complete problem X is polynomial reducible
to a problem Y ,the Y is an NP-complete problem.
洪捷的答案是写FALSE
想请问原因是因为Y至少要比X难
所以 Y 应该是 NP-HARD吗?

作者: FRAXIS (喔喔) 2014-11-18 03:09:00

只能得出 Y 是NP-Hard 没办法证明 Y 是 NPC

作者: john35452 (小杰) 2014-11-24 22:51:00

回得有点慢，要证明NP-complete，得先证明它属于NP，再找到一已知NPC问题可reduce至此问题，才能证明，所以这题也可以说是还要证明Y属于NP

继续阅读

Re: [理工] 作业系统的process forking原理HiltonCool [理工] 作业系统的process forking原理ifooleru Fw: [微积] 一题积分及一题级数请教gauss760220 [理工] 电子学-多级放大器qwerty147852 [理工] 求高手解计组数题pooboy01 [理工] [机率] 假设两事件独立造成的误差vity [理工] 材料力学eric820715 [理工] 回授系统问题qwerty147852 [理工] 浮点数运算anoymouse Fw: [问题] 数位电路gauss760220