If X is in NP-complete and complement(X) is in NP, show that for all Y in NP, complement(Y) is also in NP.

I am struggling with figuring this out. I know this means Y can be reduced to X, so if I could solve X I could solve Y. I can't solve X, but I have a certifier for X and complement(X). I am having trouble combining the reductions and certifiers to find a certifier for complement(Y).


Note that

$$ A \leq B \iff \overline{A} \leq \overline{B} $$

where $\overline{A}$ denotes the complement of $A$. Indeed, if $f$ is a reduction for either side, it is also a reduction for the other side (exercise: prove this using the definition of $\leq$).

From this, your statement quickly follows.

  • $\begingroup$ Thank you. I'm just a little confused. I know that Y ≤ X since X is NP-complete and Y is NP. But if complement(Y) ≤ complement(X) wouldn't that mean that complement(X) has to be NP-complete as well? $\endgroup$
    – Dez
    Mar 15 '18 at 22:04
  • $\begingroup$ @Dez No. According to your assumptions, $\overline X$ is in NP. And anything $\leq$ something in NP must be in NP, which is what you need. You don't know if $\overline X$ is NP-complete, but it does not matter -- NP is all you need. $\endgroup$
    – chi
    Mar 15 '18 at 22:26
  • $\begingroup$ I am having trouble proving this which definition of ≤ are you using? $\endgroup$
    – Dez
    Mar 16 '18 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.