AC0

From Wikipedia, the free encyclopedia

The correct title of this article is AC0 . It features superscript or subscript characters that are substituted or omitted because of technical limitations.

AC0 is a complexity class used in circuit complexity. It is the smallest class in the AC hierarchy, and consists of all 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.

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.

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. [1] This leads us to a proof that AC0 is not equal to NC1[citation needed].

  1. ^ M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory, 17:13–27, 1984.
Retrieved from "http://en.wikipedia.org../../../a/c/0/AC0_129f.html"