Content deleted Content added
m fix capitalization |
|||
Line 9:
==Uniformity==
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 so that each individual circuit can be computed by some [[computational resource|resource-bounded]] Turing machine; a typical requirement is that the machine has running time polynomial in ''n''.
==History==
| |||