Circuit complexity: Difference between revisions

Revision as of 05:59, 5 February 2025

Revision as of 09:38, 2 April 2025

Line 1:

{{Short description|Model of computational complexity}}

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

[[File:Three input boolean circuit.svg|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).