Circuit complexity

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 the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits ${\displaystyle C_{1},C_{2},\ldots }$ (see below).

Proving lower bounds on size of Boolean circuits computing explicit Boolean functions is a popular approach to separating complexity classes. For example, a prominent circuit class P/poly consists of Boolean functions computable by circuits of polynomial size. Proving that ${\displaystyle {\mathsf {NP}}\not \subseteq {\mathsf {P/poly}}}$ would separate P and NP (see below).

Complexity classes defined in terms of Boolean circuits include AC⁰, AC, TC⁰, NC¹, NC, and P/poly.

A Boolean circuit with ${\displaystyle 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 labelled by one of the ${\displaystyle n}$ input bits, an AND gate, an OR gate, or a NOT gate. One of these gates is designated as the output gate. Such a circuit naturally computes a function of its ${\displaystyle 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.

There are two major notions of circuit complexity. The circuit-size complexity of a Boolean function ${\displaystyle f}$ is the minimal size of any circuit computing ${\displaystyle f}$. The circuit-depth complexity of a Boolean function ${\displaystyle f}$ is the minimal depth of any circuit computing ${\displaystyle f}$.

These notions generalize when one considers the circuit complexity of any language that contains strings with different bit lengths, especially infinite formal languages. 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 ${\displaystyle C_{1},C_{2},\ldots }$ where each ${\displaystyle C_{n}}$ accepts inputs of size ${\displaystyle n}$. Each circuit family will naturally generate the language by circuit ${\displaystyle C_{n}}$ outputting ${\displaystyle 1}$ when a length ${\displaystyle n}$ string is a member of the family, and ${\displaystyle 0}$ otherwise. We say that a family of circuits is size minimal if there is no other family that decides on inputs of any size, ${\displaystyle n}$, with a circuit of smaller size than ${\displaystyle C_{n}}$ (respectively for depth minimal families). Thus, circuit complexity is meaningful even for non-recursive languages. The notion of a uniform family enables variants of circuit complexity to be related to algorithm based complexity measures of recursive languages. 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.

Hence, the circuit-size complexity of a formal language ${\displaystyle A}$ is defined as the function ${\displaystyle t:\mathbb {N} \to \mathbb {N} }$, that relates a bit length of an input, ${\displaystyle n}$, to the circuit-size complexity of a minimal circuit ${\displaystyle C_{n}}$ that decides whether inputs of that length are in ${\displaystyle A}$. The circuit-depth complexity is defined similarly.

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 ${\displaystyle C_{1},C_{2},\dots }$ where each ${\displaystyle C_{n}}$ is the circuit handling inputs of n bits. 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 ${\displaystyle C_{n}}$. 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 AC⁰ or TC⁰. When no resource bounds are specified, a language is recursive (i.e., decidable by a Turing machine) if and only if the language is decided by a uniform family of Boolean circuits.