大门| 2008年大门|问题11

对于问题X和Y，Y是NP完全的，X在多项式时间内退化为Y。以下哪项是正确的？ （A） 如果X可以在多项式时间内求解，那么Y也可以 （B） X是NP完全的 （C） X是NP难的 （D） X是NP，但不一定是NP完全的 答复: （D） 说明：

为了在GATE中解决这类问题，我们将给出两个重要定理。这些证据超出了本解释的范围。有关证明，请参阅托马斯·科尔曼的算法简介。

定理-1 当一个给定的困难问题（NPC、NPH和不可判定问题）在多项式时间内化为一个未知问题时，未知问题也变得困难。

案例1 当NPC（NP完全）问题化简为未知问题时，未知问题变成NPH（NP难）。

案例2 当NPH（NP-Hard）问题化为未知问题时，未知问题就变成了NPH（NP-Hard）。

案例3 当不可判定问题化为未知问题时，未知问题也变得不可判定。

记住，对于这个定理，困难的问题需要转换，但不是相反。

定理2

当一个未知问题在多项式时间内简化为一个简单问题（P或NP）时，未知问题也变得简单。

案例1 当一个未知问题归结为P型问题时，未知问题也变成了P型问题。

案例2 当一个未知问题归结为NP型问题时，未知问题也变成了NP。

记住，未知问题需要转换才能使这个定理起作用，但不是相反。

在给定的问题中，未知问题X在多项式时间内被简化为NPC问题，因此定理1将不起作用。但是所有的NPC问题也是NP问题，所以我们可以说X正被简化为一个已知的NP问题，所以 定理2 是适用的，X也是NP。为了使它成为NPC，我们必须先证明它是NPH，但事实并非如此，因为Y并没有减少到X。

这个解决方案是由 Pranjul Ahuja .

这个问题的小测验