Content deleted Content added
| (One intermediate revision by one other user not shown) | |||
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).
Line 27:
===Logspace uniform===
A family of Boolean circuits <math>\{C_n:n \in \mathbb{N}\}</math> is ''[[Log-space reduction|logspace uniform]]'' if there exists a [[deterministic Turing machine]] ''M'', such that
* ''M'' runs in logarithmic work space (i.e. ''M'' is a [[log-space transducer]])
* For all <math>n \in \mathbb{N}</math>, ''M'' outputs a description of <math>C_n</math> on input <math>1^n</math>
| |||