5
$\begingroup$

In the proof of Theorem 1 in this paper by Chen, McKay, Murray, and Williams the authors assume $\mathsf{NP} \subset \mathsf{P}/\mathsf{poly}$ and (in different parts of the proof) state this implies the following two inclusions:

  1. $\Sigma_3 \mathsf{TIME}(n^c) \subset \mathsf{SIZE}(n^{O(c)})$ for every $c$
  2. $\mathsf{ZPP}^\mathsf{NP} \subset \mathsf{P}/\mathsf{poly}$

They also cite this enhancement of the Karp-Lipton theorem, in which the collapse of $\mathsf{PH}$ is to $\mathsf{ZPP}^\mathsf{NP}$. I suspect the theorem is behind the inclusions in some way, but I just can't make the connection.

What am I missing?

$\endgroup$
5
$\begingroup$

If $\mathsf{NP} \subseteq \mathsf{P}/\mathsf{poly}$, then $\mathsf{SAT} \in \mathsf{SIZE}[O(n^k)]$ for some fixed constant $k$. The claimed results should follow by using this circuit to replace the $\mathsf{NP}$ oracle(s) involved in the relevant classes. For example, (2) follows by noting that $\mathsf{ZPP}^{\mathsf{NP}} = \mathsf{ZPP}^{\mathsf{SAT}}$ and then replacing every call to the $\mathsf{SAT}$ oracle with the assumed small circuit for $\mathsf{SAT}$.

$\endgroup$

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.