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

We prove that if every problem in NP has n(k)-size circuits for a fixed constant k, then for every N P-verifier and every yes-instance x of length n for that verifier, the verifier's search space has an nO(k(3))-size witness circuit: a witness for x that can be encoded with a circuit of only nO(k(3)) size. An analogous statement is proved for nondeterministic quasi-polynomial time, i.e., NQP = NTIME [n[(logO(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 N EXP. 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 N P. To illustrate, applying known algorithms for satisfiability of ACC o TH R circuits [R. Williams, STOC 2014] we conclude that for every fixed k, NQP does not have n(logk) (n)-size ACC o TH R circuits.