<p>The class $P^{SAT}$ contains $coNP$, so assuming $NP \ne coNP$, it cannot be contained in $NP$.</p>

<p>On the other hand, if $NP = coNP$, then $P^{SAT}$ <em>is</em> contained in $NP$: if $NP = coNP$, then the polynomial hierarchy collapses to $NP$, and since $P^{SAT}$ is contained in $\Sigma_2$, it would collapse to $NP$ as well.</p>

<p>A more direct way to see it is as follows: Let $L\in P^{SAT}$ and let $M$ be a machine that decides it. The $NP$-proof system for $L$ works as follows. Given an input $x \in L$, the prover will provide the verifier the transcript of the run of $M$ on $x$, including the answer to each oracle query of $M$ and a proof that this answer is correct (such a proof exists for every answer by the assumption that $NP = coNP$).</p>

CC BY-SA 4.0
2018-05-22T07:35:26.793Z
2018-05-22T07:35:26.793Z
Or Meir
<p>Is this known? Trivially, $NP \subseteq P^{SAT}$ as any problem in $NP$ is poly-time reducible to $SAT$. I am not quite sure about the other direction especially because the $NP$ machine would require verifying the 'No' answers of the oracle which suggests $\Sigma_{2}$ (something similar to the proof of ${NP}^{NP} \subseteq \Sigma_{2}$).</p>

<cc.complexity-theory>
Is $P^{SAT} \subseteq NP$?
stillanoob
# Is $P^{SAT} \subseteq NP$?

(Asked by: username_0 on 2018-05-22)

Is this known? Trivially, $NP \subseteq P^{SAT}$ as any problem in $NP$ is poly-time reducible to $SAT$. I am not quite sure about the other direction especially because the $NP$ machine would require verifying the 'No' answers of the oracle which suggests $\Sigma\_{2}$ (something similar to the proof of ${NP}^{NP} \subseteq \Sigma\_{2}$).

**Tags:** cc.complexity-theory

---

## 1 answers

### Answer by username_1 on 2018-05-22. Score: 5 | Accepted answer

The class $P^{SAT}$ contains $coNP$, so assuming $NP \ne coNP$, it cannot be contained in $NP$.

On the other hand, if $NP = coNP$, then $P^{SAT}$ *is* contained in $NP$: if $NP = coNP$, then the polynomial hierarchy collapses to $NP$, and since $P^{SAT}$ is contained in $\Sigma\_2$, it would collapse to $NP$ as well.

A more direct way to see it is as follows: Let $L\in P^{SAT}$ and let $M$ be a machine that decides it. The $NP$-proof system for $L$ works as follows. Given an input $x \in L$, the prover will provide the verifier the transcript of the run of $M$ on $x$, including the answer to each oracle query of $M$ and a proof that this answer is correct (such a proof exists for every answer by the assumption that $NP = coNP$).


---

