Circuit complexity

Proving lower bounds on size of Boolean circuits computing explicit Boolean functions is a popular approach to separating complexity classes.

Complexity classes defined in terms of Boolean circuits include AC0, AC, TC0, NC1, NC, and P/poly.

Boolean circuits, however, only allow a fixed number of input bits.

Thus, no single Boolean circuit is capable of deciding such a language.

However, the non-uniform variant is helpful to find lower bounds on how complex any circuit family must be in order to decide given languages.

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.

A uniformity condition is often imposed on these families, requiring the existence of some possibly resource-bounded Turing machine that, on input n, produces a description of the individual circuit

When this Turing machine has a running time polynomial in n, the circuit family is said to be P-uniform.

The stricter requirement of DLOGTIME-uniformity is of particular interest in the study of shallow-depth circuit-classes such as AC0 or TC0.

is polynomial-time uniform if there exists a deterministic Turing machine M, such that A family of Boolean circuits

is logspace uniform if there exists a deterministic Turing machine M, such that Circuit complexity goes back to Shannon in 1949,[2] who proved that almost all Boolean functions on n variables require circuits of size Θ(2n/n).

Despite this fact, complexity theorists have so far been unable to prove a superlinear lower bound for any explicit function.

Superpolynomial lower bounds have been proved under certain restrictions on the family of circuits used.

The fact that parity is not contained in AC0 was first established independently by Ajtai in 1983[3][4] and by Furst, Saxe and Sipser in 1984.

[5] Later improvements by Håstad in 1987[6] established that any family of constant-depth circuits computing the parity function requires exponential size.

Extending a result of Razborov,[7] Smolensky in 1987[8] 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

outputs 1 if and only if the graph encoded by the string contains a clique of size k. This family of functions is monotone and can be computed by a family of circuits, but it has been shown that it cannot be computed by a polynomial-size family of monotone circuits (that is, circuits with AND and OR gates but without negation).

The original result of Razborov in 1985[7] was later improved to an exponential-size lower bound by Alon and Boppana in 1987.

[9] In 2008, Rossman[10] showed that constant-depth circuits with AND, OR, and NOT gates require size

In 1999, Raz and McKenzie later showed that the monotone NC hierarchy is infinite.

Known results include It is open whether NEXPTIME has nonuniform TC0 circuits.

Proofs of circuit lower bounds are strongly connected to derandomization.

[16] In 1997, Razborov and Rudich showed that many known circuit lower bounds for explicit Boolean functions imply the existence of so called natural properties useful against the respective circuit class.

[17] On the other hand, natural properties useful against P/poly would break strong pseudorandom generators.

This is often interpreted as a "natural proofs" barrier for proving strong circuit lower bounds.

In 2016, Carmosino, Impagliazzo, Kabanets and Kolokolova proved that natural properties can be also used to construct efficient learning algorithms.

For each non-negative integer i, there is a class NCi, consisting of polynomial-size circuits of depth

By considering unbounded fan-in gates, the classes ACi and AC (which is equal to NC) can be constructed.

Many other circuit complexity classes with the same size and depth restrictions can be constructed by allowing different sets of gates.

If the Turing Machine that accepts the language is oblivious (meaning that it reads and writes the same memory cells regardless of input), then