5

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?

jbensmai
  • 143
  • 1
  • 4

1 Answers1

11

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.

Huck Bennett
  • 4,868
  • 2
  • 33
  • 46