0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.