Content deleted Content added
Citation bot (talk | contribs) Removed parameters. | Use this bot. Report bugs. | Suggested by SemperIocundus | #UCB_webform |
m →top: \mathsf |
||
Line 5:
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).
Proving lower bounds on size of Boolean circuits computing explicit Boolean functions is a popular approach to separating complexity classes. For example, a [[P/poly#Importance of P/poly|prominent]] circuit class [[P/poly]] consists of Boolean functions computable by circuits of polynomial-size. Proving that <math>\mathsf{NP}\not\subseteq \mathsf{P/poly}</math> would separate [[P (complexity)|P]] and [[NP (complexity)|NP]] (see below).
[[Complexity class]]es defined in terms of Boolean circuits include [[AC0|AC<sup>0</sup>]], [[AC (complexity)|AC]], [[TC0|TC<sup>0</sup>]], [[NC1 (complexity)|NC<sup>1</sup>]], [[NC (complexity)|NC]], and [[P/poly]].
| |||