World's most popular travel blog for travel bloggers.

If $A$ is m-complete for $\Sigma_n$, is $\overline{A}$ m-complete for $\Pi_n$?

, , No Comments
Problem Detail: 

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.

Asked By : McAngus
Answered By : Ariel

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback