AC0

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 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.

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.

It can be shown that calculating the parity of an input cannot be decided by any AC⁰ circuits, even with non-uniformity. ^{[citation needed]} This leads us to a proof that AC⁰ is not equal to NC^{1 [citation needed]}.