The Current State of Circuit Lower Bounds
David Mix Barrington · 1990
We review the existing results showing languages to be outside of complexity classes defined by tight constraints on boolean circuits, using the new characterizations of these classes in terms of automata theory [BT88] and formal logic [BIS88]. We outline the methods and results in the case of three types of classes defined by circuits of constant depth, polynomial size, and unbounded fan-in, for three different types of gates. These are AND and OR gates [FSS84], AND, OR, and MOD-p gates [Ra87, Sm87], and modular gates alone with certain other restrictions [BST90]. Most of this survey was prepared for the McGill University Workshop in Theoretical Computer Science, held in February 1989. 2. Introduction It would be nice to show that the CLIQUE problem is not solved by a family of boolean circuits where circuit size grows polynomially with input size. This would not only show P 6= NP , but also would demonstrate our "understanding" of polynomial-size circuits in a particular sense. We ...