We prove that if every problem in N P 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 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., NQ P = N TIM E [ 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 NEX P .

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 NQ P , or even N P . To illustrate, applying known algorithms for satisfiability of AC C T H R circuits [R. Williams, STOC 2014] we conclude that for every fixed k , NQ P does not have n log k n -size AC C T H R circuits.