Mr.*_*. X 5 theory computer-science np-complete
如果已知问题X(决策问题)是NP完全的,并且证明在多项式时间内被简化为问题Y,那么你可以说问题Y是NP完全吗？
我的第一个想法是,不,问题Y需要显示它在NP中.但经过进一步思考,如果X减少到Y,则Y已经被认为是NP完全的.现在我只是困惑...任何帮助将不胜感激.
反对意见的论据：
\n\n如果 X \xe2\x88\x88 NP 且 X \xe2\x87\x94 Y 和 Y \xe2\x88\x89 NP 则 X \xe2\x88\x89 NP。
\n