Circuit complexity: Difference between revisions

Revision as of 11:23, 2 April 2020

Revision as of 09:04, 4 April 2020

Line 2:

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

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. One speaks of the circuit complexity of a Boolean circuit. 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).

[[Complexity class]]es defined in terms of Boolean circuits include [[AC0|AC⁰]], [[AC (complexity)|AC]], [[TC0|TC⁰]] and [[NC (complexity)|NC]].