The Circuit-Input Game, Natural Proofs, and Testing Circuits With Data

We revisit a natural zero-sum game from several prior works. A circuit player, armed with a collection of Boolean circuits, wants to compute a function f with one (or some) of its circuits. An input player has a collection of inputs, and wants to find one (or some) inputs on which the circuit player cannot compute f . Several results are known on the existence of small-support strategies for zero-sum games, in particular the above circuit-input game. We give two new applications of these classical results to circuit complexity: Natural properties useful against self-checking circuits are equivalent to circuit lower bounds. We show how the Natural Proofs barrier may be potentially sidestepped, by simply focusing on analyzing circuits that check their answers. Slightly more precisely, we prove N P not subset of/poly if and only if there are natural properties that (a) accept the SAT function and (b) are useful against polynomialsize circuits that never err when they report SAT. (Note, via self-reducibility, any small circuit can be turned into one of this kind!) The proof is very general; similar equivalences hold for other lower bound problems. Our message is that one should search for lower bound methods that are designed to succeed (only) against circuits with "one-sided error." Circuit Complexity versus Testing Circuits With Data. We reconsider the problem of program testing, which we formalize as deciding if a given circuit computes a (fixed) function f. We define the "data complexity" of f (as a function of circuit size s) to be the minimum cardinality of a test suite of inputs: a set of input/output pairs necessary and sufficient for deciding if any given circuit of size at most s computes a slice of f. (This is a "gray-box testing" problem, where the value s is side information.) We prove that designing small test suites for f is equivalent to proving circuit lower bounds on f: the data complexity of testing f is "small" if and only if the circuit complexity of f is "large." Therefore, circuit lower bounds may be constructively viewed as data design circuit-testing problems.