🤩 Discover new information from across the web

Circuit complexity

Model of computational complexity

Top 10 Circuit complexity related articles

Example Boolean circuit. The {\displaystyle \wedge } nodes are AND gates, the {\displaystyle \vee } nodes are OR gates, and the ¬ {\displaystyle \neg } nodes are NOT gates

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 C 1 , C 2 , {\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 N P P / p o l y {\displaystyle NP\not \subseteq P/poly} would separate P and NP (see below).

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

Circuit complexity Intro articles: 4

Size and Depth

A Boolean circuit with n {\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 n {\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 n {\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 (these are outlined in Sipser (1997)[1]:324). The circuit-size complexity of a Boolean function f {\displaystyle f} is the minimal size of any circuit computing f {\displaystyle f} . The circuit-depth complexity of a Boolean function f {\displaystyle f} is the minimal depth of any circuit computing f {\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 C 1 , C 2 , {\displaystyle C_{1},C_{2},\ldots } where each C n {\displaystyle C_{n}} accepts inputs of size n {\displaystyle n} . Each circuit family will naturally generate the language by circuit C n {\displaystyle C_{n}} outputting 1 {\displaystyle 1} when a length n {\displaystyle n} string is a member of the family, and 0 {\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, n {\displaystyle n} , with a circuit of smaller size than C n {\displaystyle C_{n}} (respectively for depth minimal families). Thus circuit complexity is meaningful even for non-recursive languages. The notion of a uniform family (see below) 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 A {\displaystyle A} is defined as the function t : N N {\displaystyle t:\mathbb {N} \to \mathbb {N} } , that relates a bit length of an input, n {\displaystyle n} , to the circuit-size complexity of a minimal circuit C n {\displaystyle C_{n}} that decides whether inputs of that length are in A {\displaystyle A} . The circuit-depth complexity is defined similarly.

Circuit complexity Size and Depth articles: 7


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 C 1 , C 2 , {\displaystyle C_{1},C_{2},\dots } where each C n {\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 C n {\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 AC0 or TC0. 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.

Polynomial-time uniform

A family of Boolean circuits { C n : n N } {\displaystyle \{C_{n}:n\in \mathbb {N} \}} is polynomial-time uniform if there exists a deterministic Turing machine M, such that

  • M runs in polynomial time
  • For all n N {\displaystyle n\in \mathbb {N} } , M outputs a description of C n {\displaystyle C_{n}} on input 1 n {\displaystyle 1^{n}}

Logspace uniform

A family of Boolean circuits { C n : n N } {\displaystyle \{C_{n}:n\in \mathbb {N} \}} is logspace uniform if there exists a deterministic Turing machine M, such that

  • M runs in logarithmic space
  • For all n N {\displaystyle n\in \mathbb {N} } , M outputs a description of C n {\displaystyle C_{n}} on input 1 n {\displaystyle 1^{n}}

Circuit complexity Uniformity articles: 6


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 only been able to prove superpolynomial circuit lower bounds on functions explicitly constructed for the purpose of being hard to calculate.

More commonly, 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)[2] and by Furst, Saxe and Sipser (1984).[3] Later improvements by Håstad (1987) in fact establish that any family of constant-depth circuits computing the parity function requires exponential size. Extending a result of Razborov, 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 ( n 2 ) {\displaystyle {n \choose 2}} bits, which indicate for each possible edge whether it is present. Then the k-clique problem is formalized as a function f k : { 0 , 1 } ( n 2 ) { 0 , 1 } {\displaystyle f_{k}:\{0,1\}^{n \choose 2}\to \{0,1\}} such that f k {\displaystyle f_{k}} 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 (1985) was later improved to an exponential-size lower bound by Alon and Boppana (1987). Rossman (2008) shows that constant-depth circuits with AND, OR, and NOT gates require size Ω ( n k / 4 ) {\displaystyle \Omega (n^{k/4})} to solve the k-clique problem even in the average case. Moreover, there is a circuit of size n k / 4 + O ( 1 ) {\displaystyle n^{k/4+O(1)}} that computes f k {\displaystyle f_{k}} .

Raz and McKenzie later showed that the monotone NC hierarchy is infinite (1999).

The Integer Division Problem lies in uniform TC0 (Hesse 2001).

Circuit complexity History articles: 7

Circuit lower bounds

Circuit lower bounds are generally difficult. Known results include

  • Parity is not in nonuniform AC0, proved by Ajtai (1983) and by Furst, Saxe and Sipser.
  • Uniform TC0 is strictly contained in PP, proved by Allender.
  • The classes SP
    , PP[4] and MA/1[5] (MA with one bit of advice) are not in SIZE(nk) for any constant k.
  • While it is suspected that the nonuniform class ACC0 does not contain the majority function, it was only in 2010 that Williams proved that N E X P A C C 0 {\displaystyle {\mathsf {NEXP}}\not \subseteq {\mathsf {ACC}}^{0}} .[6]

It is open whether NEXPTIME has nonuniform TC0 circuits.

Proofs of circuit lower bounds are strongly connected to derandomization. A proof that P = B P P {\displaystyle {\mathsf {P}}={\mathsf {BPP}}} would imply that either N E X P P / p o l y {\displaystyle {\mathsf {NEXP}}\not \subseteq {\mathsf {P/poly}}} or that permanent cannot be computed by nonuniform arithmetic circuits (polynomials) of polynomial size and polynomial degree.[7]

Razborov and Rudich (1997) 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.[8] 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. Carmosino, Impagliazzo, Kabanets and Kolokolova (2016) proved that natural properties can be also used to construct efficient learning algorithms.[9]

Circuit complexity Circuit lower bounds articles: 7

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 O ( log i ( n ) ) {\displaystyle O(\log ^{i}(n))} , using bounded fan-in AND, OR, and NOT gates. We can talk about the union NC of all of these classes. By considering unbounded fan-in gates, we construct the classes ACi and AC (which is equal to NC). We may construct many other circuit complexity classes with the same size and depth restrictions by allowing different sets of gates.

Relation to time complexity

Say that a certain language, A {\displaystyle A} , belongs to the time-complexity class TIME ( t ( n ) ) {\displaystyle {\text{TIME}}(t(n))} for some function t : N N {\displaystyle t:\mathbb {N} \to \mathbb {N} } . Then A {\displaystyle A} has circuit complexity O ( t 2 ( n ) ) {\displaystyle {\mathcal {O}}(t^{2}(n))} .[1]


  1. ^ a b Sipser, M. (1997). 'Introduction to the theory of computation.' Boston: PWS Pub. Co.
  2. ^ Ajtai, Miklós; Komlós, János; Szemerédi, Endre (1983). An 0(n log n) sorting network. STOC '83 Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. pp. 1–9. ISBN 978-0-89791-099-6.
  3. ^ Furst, Merrick; Saxe, James B.; Sipser, Michael (1984). "Parity, circuits, and the polynomial-time hierarchy". Mathematical Systems Theory. 17 (1): 13–27. doi:10.1007/BF01744431. MR 0738749.
  4. ^ See proof
  5. ^ Santhanam, Rahul (2007). "Circuit lower bounds for Merlin-Arthur classes". STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. pp. 275–283. CiteSeerX doi:10.1145/1250790.1250832.
  6. ^ Williams, Ryan (2011). "Non-Uniform ACC Circuit Lower Bounds" (PDF). CCC 2011: Proceedings of the 26th Annual IEEE Conference on Computational Complexity. pp. 115–125. doi:10.1109/CCC.2011.36.
  7. ^ Kabanets, V.; Impagliazzo, R. (2004). "Derandomizing polynomial identity tests means proving circuit lower bounds". Computational Complexity. 13 (1): 1–46. doi:10.1007/s00037-004-0182-6.
  8. ^ Razborov, Alexander; Rudich, Stephen (1997). "Natural proofs". Journal of Computer and System Sciences. 55. pp. 24–35.
  9. ^ Carmosino, Marco; Impagliazzo, Russell; Kabanets, Valentine; Kolokolova, Antonina (2016). "Learning algorithms from natural proofs". Computational Complexity Conference.