4
$\begingroup$

In the polynomial hierarchy we have $\Sigma_2=NP^{NP}$ and $\Pi_2=co\Sigma_2$.

So we have $\Pi_2=co(NP^{NP})$.

Is it same as $(coNP)^{NP}$?

I just wonder why not a hierarchy with $coNP$.

$\endgroup$
  • 1
    $\begingroup$ Yes, the two are the same. You can also switch NP and coNP in the exponent if you wish. $\endgroup$ – Yuval Filmus Dec 14 '17 at 7:46
  • $\begingroup$ I see $NP^{NP}=NP^{coNP}$ if that is what you mean. $\endgroup$ – T.... Dec 14 '17 at 9:26
1
$\begingroup$

By definition, for any oracle for a language $A$, $(coNP)^{A}=\{L \mid \overline{L} \in NP^{A}\}$. Using this definition and definition of co-class we have

$$L \in co(NP^{NP})\iff \overline{L}\in NP^{NP} \iff L \in (coNP)^{NP}$$

You can also use $coNP$ instead of $NP$ as oracle (as Yuval commented), since if we can decide $x \in L$ using an oracle for a language $A$ we can decide $x \in L$ using another oracle for $\overline{A}$ as well, because $x \in A \iff x \notin \overline{A}$.

$\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.