Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma
Cody D. Murray, Ryan Williams · SIAM Journal on Computing · 2020
We prove that if every problem in ${NP}$ has $n^k$-size circuits for a fixed constant $k$, then for every ${NP}$-verifier and every yes-instance $x$ of length $n$ for that verifier, the verifier's search space has an $n^{O(k^3)}$-size witness circuit: A witness for $x$ that can be encoded with a circuit of only $n^{O(k^3)}$ size. An analogous statement is proved for nondeterministic quasi-polynomial time, i.e., ${NQP} = {NTIME}[n^{\log^{O(1)} n}]$. This significantly extends the Easy Witness Lemma of Impagliazzo, Kabanets, and Wigderson [ J. Comput. System Sci., 65 (2002), pp. 672--694] which only held for larger nondeterministic classes such as ${NEXP}$. As a consequence, the connections between circuit-analysis algorithms and circuit lower bounds can be considerably sharpened: Algorithms for approximately counting satisfying assignments for given circuits which improve over exhaustive search can imply circuit lower bounds for functions in ${NQP}$, or even ${NP}$. To illustrate, applying known algorithms for satisfiability of ${ACC} \circ {THR}$ circuits [R. Williams, New algorithms and lower bounds for circuits with linear threshold gates, in Proceedings of the 46th Annual ACM Symposium on Theory of Computing, ACM, New York, 2014, pp. 194--202] we conclude that for every fixed $k$, ${NQP}$ does not have $n^{\log^k n}$-size ${ACC} \circ {THR}$ circuits.