Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
If we have a set $A$ that is m-complete for $\Sigma_n$, then is it's complement $\overline{A}$ m-complete for $\Pi_n$?
I know that $\overline{A} \in \Pi_n$, but does it inherit the completeness?
I think this makes sense but I can't seem to think of any formal reasons why.
Hint: use the fact that $A\le_p B \iff \overline{A} \le_p \overline{B}$ (the same reduction works for both sides).
Try proving this for $NP,coNP$ first, and then check if your proof generalizes to the n'th level too.
