Circuit complexity: Difference between revisions

Revision as of 20:28, 27 October 2006

Revision as of 20:56, 29 October 2006

Line 9:

==Uniformity==

EachBoolean particularcircuits circuitare mustone haveof somethe fixed,prime finiteexamples inputof size;so-called this[[uniformity is very different from(complexity)|non-uniform]] [[Turingabstract machine|models of computation]]s andin otherthe modelssense that inputs of computationdifferent lenghts are processed by different circuits, in contrast with uniform models such as [[Turing machine]]s where the same computational device canis operateused onfor inputsall ofpossible anyinput sizelengths. An individual [[computational problem]] is thus associated with a particular ''family'' of boolean circuits. <math>C_1, WeC_2, often... require</math> thatwhere thereeach <math>C_n</math> is somethe circuit handling inputs of ''n'' bits. A [[uniformity (complexity)|uniformity]] condition is often imposed on thethese difficultyfamilies ofso analyzingthat each individual circuit can be computed by some [[computational resource|resource-bounded]] Turing machine.

==History==

In his 1999 book on circuit complexity, Vollmer states (pg. 1) that "the direction which ''complexity theoretic research on circuits'' took was heavily influenced by Savage's textbook", citing Savage 1976.

===Key results===

*The boolean function PARITY which is 1 if and only if the sum of its input bits does not lie in <math>AC^0</math>. The result was first established independently by Ajtai (1983) and by Furst, Saxe and Sipser (1984). Later improvements by Hastad (1987) in fact establish that any family of <math>AC^0</math> computing PARITY requires exponential size. Smolensky (1986) proved that this is true even if the circuit is augmented with gates computing the sum of its input bits modulo some prime p.

*The monotone function CLIQUE cannot be computed by a polynomial-size family of monotone circuits (that is, circuits with AND and OR gates but no negation). This original result of [[Alexander Razborov|Razborov]] (1985) was later improved to an exponential-size lower bound by Alon and Boppana (1987). Raz and McKenzie later showed that the monotone NC hierarchy is infinite (1999).

*Division lies in uniform [[TC0]] (Hesse 2001).

==References==