# Why not a $coNP$ hierarchy?

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

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

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