<p>The answer is "no".</p>

<p>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$. </p>

<p>Two interesting containment chains are:</p>

<p>$NP \subseteq \Delta_2^P \subseteq S_2^P \subseteq \Sigma_2^P \cap \Pi_2^P \subseteq \Pi_2^P$</p>

<p>and</p>

<p>$NP \subseteq MA \subseteq BP \cdot NP = AM \subseteq \Pi_2^P$</p>

<p>To help clarify the letter soup, see Wikipedia's article on the <a href="http://en.wikipedia.org/wiki/Arthur%E2%80%93Merlin_protocol" rel="nofollow noreferrer">Arthur-Merlin protocol</a> and <a href="http://en.wikipedia.org/wiki/S2P_%28complexity%29" rel="nofollow noreferrer">$S_2^P$</a>. There's also of course the <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo" rel="nofollow noreferrer">complexity zoo</a> for descriptions of these various classes.</p>

<p>Also take a look at <a href="https://cstheory.stackexchange.com/questions/3890/canonical-complete-problems-for-deltap-n">this question</a> asking about canonical $\Delta_i^P$-complete problems.</p>

CC BY-SA 3.0
2012-09-25T07:03:28.607Z
Thank you very much for the pointers, I'll make sure to check them out.
jbensmai
CC BY-SA 3.0
2012-09-25T05:33:40.747Z
2012-09-25T16:22:10.860Z
2017-04-13T12:32:28.053Z
Huck Bennett
<p>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?</p>

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

CC BY-SA 3.0
2012-09-24T16:12:27.630Z
Please check [generalized Ladner’s theorem](http://cstheory.stackexchange.com/questions/799/generalized-ladners-theorem).
Tsuyoshi Ito
<cc.complexity-theory><np-hardness><complexity-classes>
What if a problem is both in $\Pi_2^p$ and $NP$-hard?
jbensmai
# What if a problem is both in $\Pi_2^p$ and $NP$-hard?

(Asked by: username_0 on 2012-09-24)

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?

**Tags:** cc.complexity-theory, np-hardness, complexity-classes
> **Comments:**
> **username_1**: Please check [generalized Ladner’s theorem](http://cstheory.stackexchange.com/questions/799/generalized-ladners-theorem).  

---

## 1 answers

### Answer by username_2 on 2012-09-25. Score: 11 | Accepted answer

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](http://en.wikipedia.org/wiki/Arthur%E2%80%93Merlin_protocol) and [$S\_2^P$](http://en.wikipedia.org/wiki/S2P_%28complexity%29). There's also of course the [complexity zoo](http://qwiki.stanford.edu/index.php/Complexity_Zoo) for descriptions of these various classes.

Also take a look at [this question](https://cstheory.stackexchange.com/questions/3890/canonical-complete-problems-for-deltap-n) asking about canonical $\Delta\_i^P$-complete problems.

> **Comments:**
> **username_0**: Thank you very much for the pointers, I'll make sure to check them out.  

---

