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, there exists 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 of THR circuits [R Williams STOC 2014], we conclude that for every fixed k, NQP does not have n^(log^k n)-size ACC of THR circuits.