5
$\begingroup$

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?

$\endgroup$
11
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.