Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR17-188 | 22nd December 2017 22:36

#### Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP

TR17-188
Authors: Cody Murray, Ryan Williams
Publication: 23rd December 2017 16:14
Keywords:

Abstract:

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 [JCSS'02] 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 to 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, STOC 2014] we conclude that for every fixed \$k\$, \$NQP\$ does not have \$n^{\log^k n}\$-size \$ACC \circ THR\$ circuits.

ISSN 1433-8092 | Imprint