AC0
AC0 is a complexity class used in circuit complexity. It is the smallest class in the AC hierarchy, and consists of all families of circuits of depth O(1) and polynomial size, with unlimited-fanin AND gates and OR gates. (We allow NOT gates 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 the BIT operator, or alternatively by FO(+, 
), or by Turing machine in the logarithmic hierarchy.[1]
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. [2] It follows that AC0 is not equal to NC1, because a family of circuits in the latter class can compute parity.
[edit] References
- ^ *N. Immerman Descriptive complexity (1999 Springer), page 85.
- ^ M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory, 17:13–27, 1984.
|
|||||||||||||||||
