Does $NP^{SAT}=NP^{NP}$?
We can see easily that $NP^{SAT}\subseteq NP^{NP}$, because $SAT \in NP$.
But is the other side $NP^{NP}\subseteq NP^{SAT}$ also true? If yes, how can we prove it?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Yes, because $\mathsf{SAT}$ is $\mathsf{NP}$-complete.
Let $L\in\mathsf{NP}^\mathsf{NP}$. This means that there exists $A\in\mathsf{NP}$ such that $L\in\mathsf{NP}^A$. But you can replace any oracle query to the set $A$ with a polynomial-time deterministic computation that uses oracle queries to $\mathsf{SAT}$. Thus, $L\in\mathsf{NP}^\mathsf{SAT}$.
