Circuit complexity: Difference between revisions

Revision as of 21:17, 8 February 2022

Revision as of 12:41, 28 February 2022

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⁰]], [[AC (complexity)|AC]], [[TC0|TC⁰]], [[NC1 (complexity)|NC¹]], [[NC (complexity)|NC]], and [[P/poly]].