# What if a problem is both in $\Pi_2^p$ and $NP$-hard?

If a problem $P$ belongs to both $\Pi_2^p$ and $NP$-hard (thanks to some reduction from a $NP$-complete problem) but not to $NP$, does it imply that $P$ is $\Pi_2^p$-complete?

If the answer is no, are there some problems with these properties which have not been shown to be $\Pi_2^p$-complete?

In fact, in addition to the general argument pointed to by Tsuyoshi, there are a number of well-studied complexity classes which contain NP, but are contained in $\Pi_2^P$.

Two interesting containment chains are:

$NP \subseteq \Delta_2^P \subseteq S_2^P \subseteq \Sigma_2^P \cap \Pi_2^P \subseteq \Pi_2^P$

and

$NP \subseteq MA \subseteq BP \cdot NP = AM \subseteq \Pi_2^P$

To help clarify the letter soup, see Wikipedia's article on the Arthur-Merlin protocol and $S_2^P$. There's also of course the complexity zoo for descriptions of these various classes.

Also take a look at this question asking about canonical $\Delta_i^P$-complete problems.

• Thank you very much for the pointers, I'll make sure to check them out. – jbensmai Sep 25 '12 at 7:03