Succinct representations of Boolean functions and the Circuit-SAT problem

Abstract

We study the question whether there is a computational advantage in deciding properties of Boolean functions given a succinct description of the function (such as a Boolean circuit) as opposed to black-box access to the function. We argue that a significant computational advantage for a large class of properties implies a non-trivial algorithm for the Circuit Satisfiability (Circuit-SAT) problem. In particular, we show that if there is a property with strong black-box lower bounds yet decidable in BPP, which also has a highly sensitive instance computable by a small circuit, then there is a non-uniform sub-exponential algorithm for the Circuit-SAT problem. Additionally, we analyze variants of this question for other computational models.