Circuit complexity

Last updated

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 Three input boolean circuit.svg
Example Boolean circuit. The nodes are AND gates, the nodes are OR gates, and the 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 (see below).

Contents

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 would separate P and NP (see below).

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

Size and depth

A Boolean circuit with 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 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 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 [1] The circuit-size complexity of a Boolean function is the minimal size of any circuit computing . The circuit-depth complexity of a Boolean function is the minimal depth of any circuit computing .

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 where each accepts inputs of size . Each circuit family will naturally generate the language by circuit outputting when a length string is a member of the family, and otherwise. We say that a family of circuits is size minimal if there is no other family that decides on inputs of any size, , with a circuit of smaller size than (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 is defined as the function , that relates a bit length of an input, , to the circuit-size complexity of a minimal circuit that decides whether inputs of that length are in . The circuit-depth complexity is defined similarly.

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 where each 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 . 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 is polynomial-time uniform if there exists a deterministic Turing machine M, such that

Logspace uniform

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

History

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 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 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 bits, which indicate for each possible edge whether it is present. Then the k-clique problem is formalized as a function such that 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 to solve the k-clique problem even in the average case. Moreover, there is a circuit of size that computes .

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

The Integer Division Problem lies in uniform TC0. [12]

Circuit lower bounds

Circuit lower bounds are generally difficult. Known results include

It is open whether NEXPTIME has nonuniform TC0 circuits.

Proofs of circuit lower bounds are strongly connected to derandomization. A proof that would imply that either or that permanent cannot be computed by nonuniform arithmetic circuits (polynomials) of polynomial size and polynomial degree. [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. [18]

Complexity classes

Many circuit complexity classes are defined in terms of class hierarchies. For each non-negative integer i, there is a class NCi, consisting of polynomial-size circuits of depth , using bounded fan-in AND, OR, and NOT gates. The union NC of all of these classes is a subject to discussion. 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.

Relation to time complexity

If a certain language, , belongs to the time-complexity class for some function , then has circuit complexity . If the Turing Machine that accepts the language is oblivious (meaning that it reads and writes the same memory cells regardless of input), then has circuit complexity . [19]

Monotone circuits

A monotone Boolean circuit is one that has only AND and OR gates, but no NOT gates. A monotone circuit can only compute a monotone Boolean function, which is a function where for every , , where means that for all .

See also

Notes

  1. See proof.

Related Research Articles

<span class="mw-page-title-main">BQP</span> Computational complexity class of problems

In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. It is the quantum analogue to the complexity class BPP.

In computational complexity theory, the class NC (for "Nick's Class") is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In other words, a problem with input size n is in NC if there exist constants c and k such that it can be solved in time O((log n)c) using O(nk) parallel processors. Stephen Cook coined the name "Nick's class" after Nick Pippenger, who had done extensive research on circuits with polylogarithmic depth and polynomial size.

In theoretical computer science, communication complexity studies the amount of communication required to solve a problem when the input to the problem is distributed among two or more parties. The study of communication complexity was first introduced by Andrew Yao in 1979, while studying the problem of computation distributed among several machines. The problem is usually stated as follows: two parties each receive a -bit string and . The goal is for Alice to compute the value of a certain function, , that depends on both and , with the least amount of communication between them.

<span class="mw-page-title-main">Complexity class</span> Set of problems in computational complexity theory

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory.

In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input. This appears to have been first demonstrated in Gurevich, Stockmeyer & Vishkin (1984). The first systematic work on parameterized complexity was done by Downey & Fellows (1999).

In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.

In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. The hierarchy can be defined using oracle machines or alternating Turing machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic. The union of the classes in the hierarchy is denoted PH.

In computational complexity theory, a natural proof is a certain kind of proof establishing that one complexity class differs from another one. While these proofs are in some sense "natural", it can be shown that no such proof can possibly be used to solve the P vs. NP problem.

In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in (asymptotically) more space, subject to certain conditions. For example, a deterministic Turing machine can solve more decision problems in space n log n than in space n. The somewhat weaker analogous theorems for time are the time hierarchy theorems.

In theoretical computer science and cryptography, a pseudorandom generator (PRG) for a class of statistical tests is a deterministic procedure that maps a random seed to a longer pseudorandom string such that no statistical test in the class can distinguish between the output of the generator and the uniform distribution. The random seed itself is typically a short binary string drawn from the uniform distribution.

<span class="mw-page-title-main">Boolean circuit</span> Model of computation

In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible input length.

TC0 is a complexity class used in circuit complexity. It is the first class in the hierarchy of TC classes.

ACC<sup>0</sup>

ACC0, sometimes called ACC, is a class of computational models and problems defined in circuit complexity, a field of theoretical computer science. The class is defined by augmenting the class AC0 of constant-depth "alternating circuits" with the ability to count; the acronym ACC stands for "AC with counters". Specifically, a problem belongs to ACC0 if it can be solved by polynomial-size, constant-depth circuits of unbounded fan-in gates, including gates that count modulo a fixed integer. ACC0 corresponds to computation in any solvable monoid. The class is very well studied in theoretical computer science because of the algebraic connections and because it is one of the largest concrete computational models for which computational impossibility results, so-called circuit lower bounds, can be proved.

In computational complexity theory, arithmetic circuits are the standard model for computing polynomials. Informally, an arithmetic circuit takes as inputs either variables or numbers, and is allowed to either add or multiply two expressions it has already computed. Arithmetic circuits provide a formal way to understand the complexity of computing polynomials. The basic type of question in this line of research is "what is the most efficient way to compute a given polynomial ?"

In Boolean algebra, a parity function is a Boolean function whose value is one if and only if the input vector has an odd number of ones. The parity function of two inputs is also known as the XOR function.

In computational complexity the decision tree model is the model of computation in which an algorithm is considered to be basically a decision tree, i.e., a sequence of queries or tests that are done adaptively, so the outcome of previous tests can influence the tests performed next.

In theoretical computer science, and specifically computational complexity theory and circuit complexity, TC is a complexity class of decision problems that can be recognized by threshold circuits, which are Boolean circuits with AND, OR, and Majority gates. For each fixed i, the complexity class TCi consists of all languages that can be recognized by a family of threshold circuits of depth , polynomial size, and unbounded fan-in. The class TC is defined via

In theoretical computer science, a circuit is a model of computation in which input values proceed through a sequence of gates, each of which computes a function. Circuits of this kind provide a generalization of Boolean circuits and a mathematical model for digital logic circuits. Circuits are defined by the gates they contain and the values the gates can produce. For example, the values in a Boolean circuit are boolean values, and the circuit includes conjunction, disjunction, and negation gates. The values in an integer circuit are sets of integers and the gates compute set union, set intersection, and set complement, as well as the arithmetic operations addition and multiplication.

In computational complexity theory, Håstad's switching lemma is a key tool for proving lower bounds on the size of constant-depth Boolean circuits. It was first introduced by Johan Håstad to prove that AC0 Boolean circuits of depth k require size to compute the parity function on bits. He was later awarded the Gödel Prize for this work in 1994.

In graph theory and circuit complexity, the Tardos function is a graph invariant introduced by Éva Tardos in 1988 that has the following properties:

References

  1. Sipser, Michael (1997). Introduction to the theory of computation (1 ed.). Boston, USA: PWS Publishing Company. p. 324.
  2. Shannon, Claude Elwood (1949). "The synthesis of two-terminal switching circuits". Bell System Technical Journal . 28 (1): 59–98. doi:10.1002/j.1538-7305.1949.tb03624.x.
  3. 1 2 Ajtai, Miklós (1983). "-formulae on finite structures". Annals of Pure and Applied Logic. 24: 1–24. doi:10.1016/0168-0072(83)90038-6.
  4. 1 2 Ajtai, Miklós; Komlós, János; Szemerédi, Endre (1983). "An sorting network". Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25–27 April, 1983, Boston, Massachusetts, USA. Association for Computing Machinery. pp. 1–9. doi:10.1145/800061.808726.
  5. 1 2 Furst, Merrick L.; Saxe, James Benjamin; Sipser, Michael Fredric (1984). "Parity, circuits, and the polynomial-time hierarchy". Mathematical Systems Theory . 17 (1): 13–27. doi:10.1007/BF01744431. MR   0738749. S2CID   6306235.
  6. Håstad, Johan Torkel (1987). Computational limitations of small depth circuits (PDF) (Ph.D. thesis). Massachusetts Institute of Technology.
  7. 1 2 Razborov, Aleksandr Aleksandrovich (1985). "Lower bounds on the monotone complexity of some Boolean functions". Soviet Mathematics - Doklady . 31: 354–357. ISSN   0197-6788.
  8. Smolensky, Roman (1987). "Algebraic methods in the theory of lower bounds for Boolean circuit complexity". Proceedings of the 19th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery. pp. 77–82. doi: 10.1145/28395.28404 .
  9. Alon, Noga; Boppana, Ravi B. (1987). "The monotone circuit complexity of Boolean functions". Combinatorica . 7 (1): 1–22. CiteSeerX   10.1.1.300.9623 . doi:10.1007/bf02579196. S2CID   17397273.
  10. Rossman, Benjamin E. (2008). "On the constant-depth complexity of k-clique". STOC 2008: Proceedings of the 40th annual ACM symposium on Theory of computing. Association for Computing Machinery. pp. 721–730. doi:10.1145/1374376.1374480.
  11. Raz, Ran; McKenzie, Pierre (1999). "Separation of the monotone NC hierarchy". Combinatorica . 19 (3): 403–435. doi:10.1007/s004930050062.
  12. Hesse, William (2001). "Division is in uniform TC0". Proceedings of the 28th International Colloquium on Automata, Languages and Programming. Springer Verlag. pp. 104–114.
  13. Allender, Eric (1996). "Circuit complexity before the dawn of the new millennium". In Chandru, Vijay; Vinay, V. (eds.). Foundations of Software Technology and Theoretical Computer Science, 16th Conference, Hyderabad, India, December 18–20, 1996, Proceedings. Lecture Notes in Computer Science. Vol. 1180. Springer. pp. 1–18. doi:10.1007/3-540-62034-6_33.
  14. 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   10.1.1.92.4422 . doi:10.1145/1250790.1250832.
  15. Williams, Richard 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.
  16. Kabanets, Valentine; Impagliazzo, Russell Graham (2004). "Derandomizing polynomial identity tests means proving circuit lower bounds". Computational Complexity. 13 (1): 1–46. doi:10.1007/s00037-004-0182-6. S2CID   12451799.
  17. Razborov, Aleksandr Aleksandrovich; Rudich, Steven (1997). "Natural proofs". Journal of Computer and System Sciences . Vol. 55. pp. 24–35.
  18. Carmosino, Marco; Impagliazzo, Russell Graham; Kabanets, Valentine; Kolokolova, Antonina (2016). "Learning algorithms from natural proofs". Computational Complexity Conference.
  19. Pippenger, Nicholas; Fischer, Michael J. (1979). "Relations Among Complexity Measures". Journal of the ACM . 26 (3): 361–381. doi: 10.1145/322123.322138 . S2CID   2432526.

Further reading