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