# 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

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.

• 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?
– Dez
Mar 15 '18 at 22:04
• @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.
– chi
Mar 15 '18 at 22:26
• I am having trouble proving this which definition of ≤ are you using?
– Dez
Mar 16 '18 at 20:37