2
$\begingroup$

I was reading the following paper by Jim Kadin, "$P^{NP[O(\text{log } n)]}$ and sparse Turing complete sets for NP"

The main result is that if there is a sparse set $S \in NP$ such that $coNP \subseteq NP^S $, then $PH \subseteq P^{SAT[O(\text{log }n)]} $.

In the proof of this result he author claims that it is sufficient to prove $NP^ {SAT} \subseteq P^{SAT[O(\text{log }n)]}$ and this will imply that $PH \subseteq P^{SAT[O(\text{log }n)]} $.

I could not figure out why this is true. Perhaps this is trivial and there is some minor point (some inclusion of complexity classes) that I am missing. Please do point out why the above claim is true.

$\endgroup$
1
$\begingroup$

Simply put, even a weaker claim of $\mathrm{NP}^\mathrm{SAT}=\mathrm{NP}^\mathrm{NP}\subseteq \mathrm{P}^\mathrm{SAT}=\mathrm{P}^\mathrm{NP}$ would imply PH collapse to the second level (so even the consequence is a little bit weaker, you can adapt to your case).

We have $\mathrm{P}^\mathrm{NP}\subseteq \mathrm{co}$-$\mathrm{NP}^\mathrm{NP}$. So, from the assumption, we deduce that $\mathrm{NP}^\mathrm{NP}\subseteq \mathrm{co}$-$\mathrm{NP}^\mathrm{NP}$. As a result, PH collapse to the second level.

$\endgroup$

Your Answer

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