Search code examples
np

If X is NP-complete and Y is in NP, why Y must also be NP-complete


Suppose X and Y are decision problems for which X≤ P ​ Y, i.e., X is polynomial-time reducible to Y . If X is NP-complete and Y is in NP, why Y must also be NP-complete.


Solution

  • If X is NP complete, in particular it is NP hard, that is, every NP problem Z is polynomial-time reducible to X, which in turn is polynomial-time reducible to Y, thus Y is also NP hard. Being both NP and NP hard means you're NP complete, therefore Y is NP complete.