HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
implymathsfthesehowtwoinclusionsdoespolysubset

Problem

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:

  • $\Sigma_3 \mathsf{TIME}(n^c) \subset \mathsf{SIZE}(n^{O(c)})$ for every $c$



  • $\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?

Solution

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}$.

Context

StackExchange Computer Science Q#115318, answer score: 5

Revisions (0)

No revisions yet.