Skip to main content
deleted 6 characters in body; edited title
Source Link
dkaeae
  • 5k
  • 1
  • 16
  • 31

How does $\mathsf{NP} \subseteq\subset \mathsf{P}/\mathsf{poly}$ imply these two inclusions?

In the proof of Theorem 1 in this paper by Chen, McKay, Murray, and Williams the authors assume $\mathsf{NP} \subseteq \mathsf{P}/\mathsf{poly}$$\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) \subseteq \mathsf{SIZE}(n^{O(c)})$$\Sigma_3 \mathsf{TIME}(n^c) \subset \mathsf{SIZE}(n^{O(c)})$ for every $c$
  2. $\mathsf{ZPP}^\mathsf{NP} \subseteq \mathsf{P}/\mathsf{poly}$$\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?

How does $\mathsf{NP} \subseteq \mathsf{P}/\mathsf{poly}$ imply these two inclusions?

In the proof of Theorem 1 in this paper by Chen, McKay, Murray, and Williams the authors assume $\mathsf{NP} \subseteq \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) \subseteq \mathsf{SIZE}(n^{O(c)})$ for every $c$
  2. $\mathsf{ZPP}^\mathsf{NP} \subseteq \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?

How does $\mathsf{NP} \subset \mathsf{P}/\mathsf{poly}$ imply these two inclusions?

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?

Tweeted twitter.com/StackCompSci/status/1179139023484444674
Source Link
dkaeae
  • 5k
  • 1
  • 16
  • 31

How does $\mathsf{NP} \subseteq \mathsf{P}/\mathsf{poly}$ imply these two inclusions?

In the proof of Theorem 1 in this paper by Chen, McKay, Murray, and Williams the authors assume $\mathsf{NP} \subseteq \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) \subseteq \mathsf{SIZE}(n^{O(c)})$ for every $c$
  2. $\mathsf{ZPP}^\mathsf{NP} \subseteq \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?