Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
The answer is "no".
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.
