Circuit complexity: Difference between revisions

Revision as of 16:29, 28 January 2024

Revision as of 17:44, 13 February 2024

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).