AC⁰

From Wikipedia, the free encyclopedia

AC⁰ 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 NC⁰, which has only bounded-fanin AND and OR gates.

From a descriptive complexity viewpoint, DLOGTIME-uniform AC⁰ 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(+, ).

In 1984 Furst, Saxe, and Sipser showed that calculating the parity of an input cannot be decided by any AC⁰ circuits, even with non-uniformity. ^[1] It follows that AC⁰ is not equal to NC¹, because a family of circuits in the latter class can compute parity.

[edit] References

1. ^ M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory, 17:13–27, 1984.