Circuit complexity: Difference between revisions

Revision as of 08:16, 24 July 2023

Latest revision as of 00:57, 18 May 2025

(18 intermediate revisions by 14 users not shown)

Line 1:

{{Short description|Model of computational complexity}}

{{Use dmy dates|date=May 2019|cs1-dates=y}}

[[File:Three_input_Boolean_circuitThree input boolean circuit.jpgsvg|thumb|right|300px|Example Boolean circuit. The <math>\wedge</math> nodes are [[AND gate]]s, the <math>\vee</math> nodes are [[OR gate]]s, and the <math>\neg</math> nodes are [[NOT gate]]s.]]

In [[theoretical computer science]], '''circuit complexity''' is a branch of [[computational complexity theory]] in which [[Boolean function]]s are classified according to the size or depth of the [[Boolean circuit]]s that compute them. A related notion is the circuit complexity of a [[recursive language]] that is [[Machine that always halts|decided]] by a '''uniform''' family of circuits <math>C_{1},C_{2},\ldots</math> (see below).

Line 10:

==Size and depth==

A Boolean circuit with <math>n</math> input [[bit]]s 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 <math>n</math> 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 <math>n</math> 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.<ref name="Sipser_1997"/> The '''circuit-size complexity''' of a Boolean function <math>f</math> is the minimal size of any circuit computing <math>f</math>. The '''circuit-depth complexity''' of a Boolean function <math>f</math> is the minimal depth of any circuit computing <math>f</math>.

These notions generalize when one considers the circuit complexity of any language that contains strings with different bit lengths, especially infinite [[formal language]]s. 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 <math>C_{1},C_{2},\ldots</math> where each <math>C_{n}</math> accepts inputs of size <math>n</math>. Each circuit family will naturally generate the language by circuit <math>C_{n}</math> outputting <math>1</math> when a length <math>n</math> string is a member of the family, and <math>0</math> otherwise. We say that a family of circuits is '''size minimal''' if there is no other family that decides on inputs of any size, <math>n</math>, with a circuit of smaller size than <math>C_n</math> (respectively for '''depth minimal''' families). Thus, circuit complexity is meaningful even for [[recursive language|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.

Line 27:

===Logspace uniform===

A family of Boolean circuits <math>\{C_n:n \in \mathbb{N}\}</math> is ''[[Log-space reduction|logspace uniform]]'' if there exists a [[deterministic Turing machine]] ''M'', such that

* ''M'' runs in logarithmic work space (i.e. ''M'' is a [[log-space transducer]])

* For all <math>n \in \mathbb{N}</math>, ''M'' outputs a description of <math>C_n</math> on input <math>1^n</math>

Line 56:

==Complexity classes==

{{Unreferenced section|date=October 2024}}

Many circuit complexity classes are defined in terms of class hierarchies. For each non-negative integer ''i'', there is a class [[NC (complexity)|NCⁱ]], consisting of polynomial-size circuits of depth <math>O(\log^i(n))</math>, 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 [[AC (complexity)|ACⁱ]] 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, <math>A</math>, belongs to the [[Complexity class|time-complexity class]] <math>\text{TIME}(t(n))</math> for some function <math>t:\mathbb{N}\to\mathbb{N}</math>, then <math>A</math> has circuit complexity <math>\mathcal{O}(t(n) \log t(n))</math>. If the Turing Machine that accepts the language is [[Turing machine equivalents|oblivious]] (meaning that it reads and writes the same memory cells regardless of input), then <math>A</math> has circuit complexity <math>\mathcal{O}(t(n))</math>.<ref>{{cite journal|first1=Nicholas|last1=Pippenger|authorlink=Nick Pippenger|first2=Michael J.|last2=Fischer|authorlink2=Michael J. Fischer|title=Relations Among Complexity Measures|journal=[[Journal of the ACM]]|year=1979|volume=26|issue=3|pages=361–381|doi=10.1145/322123.322138|s2cid=2432526 |doi-access=free}}

</ref>

==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 <math>f:\{0,1\}^n \to \{0,1\}</math> where for every <math>x,y \in \{0,1\}^n</math>, <math>x \leq y \implies f(x) \leq f(y)</math>, where <math>x\leq y</math> means that <math>x_i \leq y_i</math> for all <math>i \in \{1,\ldots,n\}</math>.

==See also==

Line 73 ⟶ 77:

{{reflist|refs=

<ref name="Sipser_1997">{{cite book |author-last=Sipser |author-first=Michael |author-link=Michael Sipser |date=1997 |title=Introduction to the theory of computation |publication-place=Boston, USA |edition=1 |isbn= |publisher=PWS Publishing Company |page=324}}</ref>

<ref name="Ajtai-Komlós-Szemerédi_1983">{{cite book

<ref name="Ajtai-Komlós-Szemerédi_1983">{{cite book |author-last1=Ajtai |author-first1=Miklós |author-link1=Miklós Ajtai |author-last2=Komlós |author-first2=János |author-last3=Szemerédi |author-first3=Endre |title=An 0(n log n) sorting network |journal=STOC '83 Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing |pages=1–9 |date=1983 |isbn=978-0-89791-099-6}}</ref>

| last1 = Ajtai | first1 = Miklós | author1-link = Miklós Ajtai

<ref name="Ajtai_1983">{{cite journal |author-first=Miklós |author-last=Ajtai |author-link=Miklós Ajtai |title=<math>\Sigma^1_1</math>-formulae on finite structures |journal=Annals of Pure and Applied Logic |date=1983 |volume=24 |pages=1–24 |doi=10.1016/0168-0072(83)90038-6|doi-access=free }}</ref>

| last2 = Komlós | first2 = János | author2-link = János Komlós (mathematician)

| last3 = Szemerédi | first3 = Endre | author3-link = Endre Szemerédi

| contribution = An <math>O(n\log n)</math> sorting network

| doi = 10.1145/800061.808726

| pages = 1–9

| publisher = Association for Computing Machinery

| title = Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25–27 April, 1983, Boston, Massachusetts, USA

| year = 1983}}</ref>

<ref name="Ajtai_1983">{{cite journal |author-first=Miklós |author-last=Ajtai |author-link=Miklós Ajtai |title=<math>\Sigma^1_1</math>-formulae on finite structures |journal=Annals of Pure and Applied Logic |date=1983 |volume=24 |pages=1–24 |doi=10.1016/0168-0072(83)90038-6|doi-access=free }}</ref>

<ref name="Furst-Saxe-Sipser_1984">{{cite journal |author-last1=Furst |author-first1=Merrick L. |author-last2=Saxe |author-first2=James Benjamin |author-link2=James Benjamin Saxe |author-last3=Sipser |author-first3=Michael Fredric |author-link3=Michael Fredric Sipser |doi=10.1007/BF01744431 |issue=1 |journal=[[Mathematical Systems Theory]] |mr=738749 |pages=13–27 |title=Parity, circuits, and the polynomial-time hierarchy |volume=17 |date=1984|s2cid=6306235 }}</ref>

<ref name="Santhanam_2007">{{cite conference |author-last=Santhanam |author-first=Rahul |url=http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.111.1811 |title=Circuit lower bounds for Merlin-Arthur classes |book-title=STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing |date=2007 |pages=275–283 |doi=10.1145/1250790.1250832 |citeseerx=10.1.1.92.4422}}</ref>

Line 83 ⟶ 96:

<ref name="Hesse_2001">{{cite conference |author-first=William |author-last=Hesse |title=Division is in uniform TC⁰ |date=2001 |pages=104–114 |book-title=Proceedings of the 28th International Colloquium on Automata, Languages and Programming |publisher=[[Springer Verlag]]}}</ref>

<ref name="Raz-McKenzie_1999">{{cite journal |author-first1=Ran |author-last1=Raz |author-link1=Ran Raz |author-first2=Pierre |author-last2=McKenzie |title=Separation of the monotone NC hierarchy |journal=[[Combinatorica]] |volume=19 |number=3 |date=1999 |pages=403–435 |doi=10.1007/s004930050062}}</ref>

<ref name="Allender_1997">{{cite book

<ref name="Allender_1997">{{cite web |url=http://ftp.cs.rutgers.edu/pub/allender/fsttcs.pdf |title=Circuit Complexity before the Dawn of the New Millennium |date=1997 |editor-first=Eric Warren |editor-last=Allender |editor-link=Eric Warren Allender}} [http://ftp.cs.rutgers.edu/pub/allender/fsttcs.96.slides.ps] (NB. A 1997 survey of the field by Eric Allender.)</ref>

| last = Allender | first = Eric | author-link = Eric Allender

<ref name="Shannon_1949">{{cite journal |author-last=Shannon |author-first=Claude Elwood |author-link=Claude Elwood Shannon |title=The synthesis of two-terminal switching circuits |journal=[[Bell System Technical Journal]] |date=1949 |volume=28| number=1 |pages=59–98 |doi=10.1002/j.1538-7305.1949.tb03624.x}}</ref>

| editor1-last = Chandru | editor1-first = Vijay

| editor2-last = Vinay | editor2-first = V.

| contribution = Circuit complexity before the dawn of the new millennium

| doi = 10.1007/3-540-62034-6_33

| pages = 1–18

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Foundations of Software Technology and Theoretical Computer Science, 16th Conference, Hyderabad, India, December 18–20, 1996, Proceedings

| volume = 1180

| year = 1996| isbn = 978-3-540-62034-1 }}</ref><ref name="Shannon_1949">{{cite journal |author-last=Shannon |author-first=Claude Elwood |author-link=Claude Elwood Shannon |title=The synthesis of two-terminal switching circuits |journal=[[Bell System Technical Journal]] |date=1949 |volume=28| number=1 |pages=59–98 |doi=10.1002/j.1538-7305.1949.tb03624.x}}</ref>

<ref name="Håstad_1987">{{cite book |author-first=Johan Torkel |author-last=Håstad |author-link=Johan Torkel Håstad |title=Computational limitations of small depth circuits |date=1987 |type=Ph.D. thesis |publisher=Massachusetts Institute of Technology |url=http://www.nada.kth.se/~johanh/thesis.pdf}}</ref>

<ref name="Razborov_1985">{{cite journal |author-first=Aleksandr Aleksandrovich |author-last=Razborov |author-link=Aleksandr Aleksandrovich Razborov |title=Lower bounds on the monotone complexity of some Boolean functions |date=1985 |journal=[[Soviet Mathematics - Doklady]] |issn=0197-6788 |volume=31 |pages=354–357}}</ref>