AC0

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 predicate, or alternatively by FO(+, ×), or by Turing machine in the logarithmic hierarchy.

[4] In 1984 Furst, Saxe, and Sipser showed that calculating the parity of the input bits (unlike the aforementioned addition/subtraction problems above which had two inputs) cannot be decided by any AC0 circuits, even with non-uniformity.

[5][1] It follows that AC0 is not equal to NC1, because a family of circuits in the latter class can compute parity.

[1] More precise bounds follow from switching lemma.

Using them, it has been shown that there is an oracle separation between the polynomial hierarchy and PSPACE.

Diagram of an AC 0 circuit: The n input bits are on the bottom and the top gate produces the output; the circuit consists of AND- and OR-gates of polynomial fan-in each, and the alternation depth is bounded by a constant.