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 Boolean circuits that compute them.

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 ${\displaystyle f_{1},f_{2},\dots }$ where each ${\displaystyle f_{n}}$ is a function of n bits.

Complexity classes defined in terms of Boolean circuits include AC⁰, AC, TC⁰ 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 ${\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 resource-bounded Turing machine which, 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⁰.

Polynomial-time uniform

A family of Boolean circuits ${\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 ${\displaystyle n\in \mathbb {N} }$ , M outputs a description of ${\displaystyle C_{n}}$  on input ${\displaystyle 1^{n}}$ 

Logspace uniform

A family of Boolean circuits ${\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 ${\displaystyle n\in \mathbb {N} }$ , M outputs a description of ${\displaystyle C_{n}}$  on input ${\displaystyle 1^{n}}$ 

History

Circuit complexity goes back to Shannon (1949), who proved that almost all Boolean functions on n variables require circuits of size Θ(2ⁿ/n). Despite this fact, complexity theorists were unable to prove circuit lower bounds for specific Boolean functions.

The first function for which superpolynomial circuit lower bounds could be shown was the parity function, which computes the sum of its input bits modulo 2. The fact that parity is not contained in AC⁰ 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 ${\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 ${\displaystyle f_{k}:\{0,1\}^{n \choose 2}\to \{0,1\}}$  such that ${\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 ${\displaystyle \Omega (n^{k/4})}$  to solve the k-clique problem even in the average case. Moreover, there is a circuit of size ${\displaystyle n^{k/4+O(1)}}$  which computes ${\displaystyle f_{k}}$ .

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

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

Complexity classes

Many circuit complexity classes are defined in terms of class hierarchies. For each nonnegative integer i, there is a class NCⁱ, consisting of polynomial-size circuits of depth ${\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 ACⁱ and AC. We construct many other circuit complexity classes with the same size and depth restrictions by allowing different sets of gates.

References

• Ajtai, Miklós (1983). "${\displaystyle \Sigma _{1}^{1}}$ -formulae on finite structures". Annals of Pure and Applied Logic. 24: 1–24.
• Alon, Noga; Boppana, Ravi B. (1987). "The monotone circuit complexity of Boolean functions". Combinatorica. 7 (1): 1–22.
• Furst, Merrick L.; Saxe, James B.; Sipser, Michael (1984). "Parity, circuits, and the polynomial-time hierarchy". Mathematical Systems Theory. 17 (1): 13–27.
• Håstad, Johan (1987), Computational limitations of small depth circuits (PDF), Ph.D. thesis, Massachusetts Institute of Technology.
• Hesse, William (2001). "Division is in uniform TC⁰". Proc. 28th International Colloquium on Automata, Languages and Programming. Springer. pp. 104–114. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
• Raz, Ran; McKenzie, Pierre (1999). "Separation of the monotone NC hierarchy". Combinatorica. 19 (3): 403–435.
• Razborov, Alexander A. (1985). "Lower bounds on the monotone complexity of some Boolean functions". Mathematics of the USSR, Doklady. 31: 354–357.
• Shannon, Claude E. (1949). "The synthesis of two-terminal switching circuits". Bell System Technical Journal. 28 (1): 59–98.
• Smolensky, Roman (1987). "Algebraic methods in the theory of lower bounds for Boolean circuit complexity". Proc. 19th Annual ACM Symposium on Theory of Computing. ACM. pp. 77–82. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
• Vollmer, Heribert (1999). Introduction to Circuit Complexity: a Uniform Approach. Springer Verlag. ISBN 3-540-64310-9.
• Wegener, Ingo (1987). The Complexity of Boolean Functions. John Wiley and Sons Ltd, and B. G. Teubner, Stuttgart. ISBN 3-519-02107-2. At the time an influental textbook on the subject, commonly known as the "Blue Book". Also available for download (PDF) at the Electronic Colloquium on Computational Complexity.
• Lecture notes for a course of Uri Zwick on circuit complexity
• Circuit Complexity before the Dawn of the New Millennium, a 1997 survey of the field by Eric Allender slides.