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?
What if a problem is both in $\Pi_2^p$ and $NP$-hard?
cc.complexity theory;np hardness;complexity classes
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.