ECCC-Report TR17-188https://eccc.weizmann.ac.il/report/2017/188Comments and Revisions published for TR17-188en-usSat, 23 Dec 2017 16:14:31 +0200
Paper TR17-188
| Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP |
Ryan Williams,
Cody Murray
https://eccc.weizmann.ac.il/report/2017/188We 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.Sat, 23 Dec 2017 16:14:31 +0200https://eccc.weizmann.ac.il/report/2017/188