[理工] 演算法

[AgentSkye56 (絲凱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嗎?


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.163.207.246
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1416241139.A.0DE.html
推 FRAXIS: 只能得出 Y 是NP-Hard  沒辦法證明 Y 是 NPC
感謝~~~~
※ 編輯: AgentSkye56 (1.160.192.250), 11/18/2014 23:28:36
推 john35452: 回得有點慢，要證明NP-complete，得先證明它屬於NP，再
→ john35452: 找到一已知NPC問題可reduce至此問題，才能證明，所以這
→ john35452: 題也可以說是還要證明Y屬於NP