Content deleted Content added
→Uniformity: "/poly" means nonuniform, using polynomially long string of advice. That's something completely different. |
→Uniformity: added defintions of polytime uniform and logspace uniform |
||
Line 10:
Boolean circuits are one of the prime examples of so-called [[uniformity (complexity)|non-uniform]] [[abstract machine|models of computation]] in the sense that inputs of different lengths are processed by different circuits, in contrast with uniform models such as [[Turing machine]]s where the same computational device is used for all possible input lengths. An individual [[computational problem]] is thus associated with a particular ''family'' of Boolean circuits <math>C_1, C_2, ... </math> where each <math>C_n</math> is the circuit handling inputs of ''n'' bits. A [[uniformity (complexity)|uniformity]] condition is often imposed on these families, requiring the existence of some [[computational resource|resource-bounded]] Turing machine which, on input ''n'', produces a description of the individual circuit <math>C_n</math>. When this Turing machine has a running time polynomial in ''n'', the circuit family is said to be P-uniform. The stricter requirement of [[DLOGTIME]]-uniformity is of particular interest in the study of shallow-depth circuit-classes such as AC<sup>0</sup> or TC<sup>0</sup>.
===Polynomial-time uniform===
A family of Boolean circuits <math>\{C_n:n \in \mathbb{N}\}</math> is ''polynomial-time uniform'' if there exists a [[deterministic Turing machine]] ''M'', such that
*''M'' runs in polynomial time
* For all <math>n \in \mathbb{N}</math>, ''M'' outputs a description of <math>C_n</math> on input <math>1^n</math>
===Logspace uniform===
A family of Boolean circuits <math>\{C_n:n \in \mathbb{N}\}</math> is ''logspace uniform'' if there exists a [[deterministic Turing machine]] ''M'', such that
*''M'' runs in logarithmic space
* For all <math>n \in \mathbb{N}</math>, ''M'' outputs a description of <math>C_n</math> on input <math>1^n</math>
==History==
| |||