- AC0
AC0 is a
complexity class used incircuit complexity . It is the smallest class in the AC hierarchy, and consists of all circuits of depth O(1) and polynomial size, with unlimited-faninAND gate s andOR gate s. (We allowNOT gate s only at the inputs). It thus contains NC0, which has only bounded-fanin AND and OR gates.From a
descriptive complexity viewpoint,DLOGTIME -uniform AC0 is equal to the descriptive class FO+BIT of all languages describable in first-order logic with the addition of theBIT operator , or alternatively by FO(+, imes).In 1984 Furst, Saxe, and Sipser showed that calculating the
parity of an input cannot be decided by any AC0 circuits, even with non-uniformity. [M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. "Math. Systems Theory", 17:13–27, 1984.] This leads us to a proof that AC0 is not equal to NC1 Fact|date=February 2007.References
Wikimedia Foundation. 2010.