In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them. One speaks of the circuit complexity of a Boolean circuit. A related notion is the circuit complexity of a recursive language that is decided by a family of circuits
Contents
- Uniformity
- Polynomial time uniform
- Logspace uniform
- History
- Circuit lower bounds
- Complexity classes
- Relation to time complexity
- References
A Boolean circuit with
There are two major notions of circuit complexity (these are outlined in Sipser (1997)). The circuit-size complexity of a Boolean function
These notions generalize when one considers the circuit complexity of a recursive language: a formal language may contain strings with many different bit lengths. Boolean circuits, however, only allow a fixed number of input bits. Thus no single Boolean circuit is capable of deciding such a language. To account for this possibility, one considers families of circuits
Hence, the circuit-size complexity of a recursive language
Complexity classes defined in terms of Boolean circuits include AC0, AC, TC0 and NC.
Uniformity
Boolean circuits are one of the prime examples of so-called non-uniform models of computation in the sense that inputs of different lengths are processed by different circuits, in contrast with uniform models such as Turing machines where the same computational device is used for all possible input lengths. An individual computational problem is thus associated with a particular family of Boolean circuits
Polynomial-time uniform
A family of Boolean circuits
Logspace uniform
A family of Boolean circuits
History
Circuit complexity goes back to Shannon (1949), who proved that almost all Boolean functions on n variables require circuits of size Θ(2n/n). Despite this fact, complexity theorists have not been able to prove superpolynomial circuit lower bounds for specific Boolean functions.
On the other hand, superpolynomial lower bounds have been proved under certain restrictions on the family of circuits used. The first function for which superpolynomial circuit lower bounds were shown was the parity function, which computes the sum of its input bits modulo 2. The fact that parity is not contained in AC0 was first established independently by Ajtai (1983) and by Furst, Saxe and Sipser (1984). Later improvements by Håstad (1987) in fact establish that any family of constant-depth circuits computing the parity function requires exponential size. Smolensky (1987) proved that this is true even if the circuit is augmented with gates computing the sum of its input bits modulo some odd prime p.
The k-clique problem is to decide whether a given graph on n vertices has a clique of size k. For any particular choice of the constants n and k, the graph can be encoded in binary using
Raz and McKenzie later showed that the monotone NC hierarchy is infinite (1999).
The Integer Division Problem lies in uniform TC0 (Hesse 2001).
Circuit lower bounds
Circuit lower bounds are generally difficult. Known results include
2, PP and MA/1 (MA with one bit of advice) are not in SIZE(nk) for any constant k.
It is open whether NEXPTIME has nonuniform TC0 circuits.
Proofs of circuit lower bounds are strongly connected to derandomization. A proof that P = BPP would imply that either
Complexity classes
Many circuit complexity classes are defined in terms of class hierarchies. For each nonnegative integer i, there is a class NCi, consisting of polynomial-size circuits of depth
Relation to time complexity
Say that a certain language,