Circuit complexity

Circuit complexity is a topic in computational complexity theory, a branch of theoretical computer science which classifies boolean functions according to the amount of computational resources needed to compute them. In circuit complexity, these resources are size and depth of boolean circuits.

A boolean circuit with n input bits is a directed acyclic graph in which every node (usually called gates in this context) is either an input node of in-degree 0 labeled by one of the n input bits, an AND gate, an OR or a NOT gate. One of these gates is designated as the output gate. Such a circuit naturally computes a function of its n inputs. The size of a circuit is the number of gates it contains and its depth is the maximal length of a path from an input gate to the output gate.

The circuit-size (respectively circuit-depth) complexity of a boolean function f is the minimal size (respectively minimal depth) of any circuit computing f. The goal of circuit complexity is to determine this optimal size/depth for natural families of boolean functions. Most often the challenge involves the study of the asymptotic behavior of size or depth complexity for sequences of boolean functions $f_{1},f_{2},...$ where each $f_{n}$ is a function of n bits.

References

• Vollmer, Heribert (1999). Introduction to Circuit Complexity: a Uniform Approach. Springer Verlag. ISBN 3-540-64310-9.
• Lecture notes for a course of Uri Zwick on circuit complexity.
• Circuit Complexity before the Dawn of the New Millenium, a 1997 survey of the field by Eric Allender