# 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).

$$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$).
• @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