Question

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?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top