AC⁰ is a

complexity class In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms o ...

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 gate The AND gate is a basic digital logic gate that implements logical conjunction (∧) from mathematical logic AND gate behaves according to the truth table. A HIGH output (1) results only if all the inputs to the AND gate are HIGH (1). If not al ...

s and

OR gate The OR gate is a digital logic gate that implements logical disjunction. The OR gate returns true if either or both of its inputs are true; otherwise it returns false. The input and output states are normally represented by different voltage lev ...

s (we allow NOT gates only at the inputs). It thus contains NC⁰, which has only bounded-fanin AND and OR gates.

Example problems

Integer addition and subtraction are computable in AC⁰, but multiplication is not (at least, not under the usual binary or base-10 representations of integers). Since it is a circuit class, like P/poly, AC⁰ also contains every unary language.

Descriptive complexity

From a

descriptive complexity ''Descriptive Complexity'' is a book in mathematical logic and computational complexity theory by Neil Immerman. It concerns descriptive complexity theory, an area in which the expressibility of mathematical properties using different types of l ...

viewpoint, DLOGTIME-

uniform A uniform is a variety of clothing worn by members of an organization while participating in that organization's activity. Modern uniforms are most often worn by armed forces and paramilitary organizations such as police, emergency services, ...

AC⁰ is equal to the descriptive class FO+BIT of all

languages Language is a structured system of communication. The structure of a language is its grammar and the free components are its vocabulary. Languages are the primary means by which humans communicate, and may be conveyed through a variety of met ...

describable in first-order logic with the addition of the

BIT predicate In mathematics and computer science, the BIT predicate or Ackermann coding, sometimes written BIT(''i'', ''j''), is a predicate that tests whether the ''j''th bit of the number ''i'' is 1, when ''i'' is written in binary. History The BIT pre ...

, or alternatively by FO(+, ×), or by

Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer alg ...

in the logarithmic hierarchy.

Separations

In 1984 Furst, Saxe, and Sipser showed that calculating the

parity Parity may refer to: * Parity (computing) ** Parity bit in computing, sets the parity of data for the purpose of error detection ** Parity flag in computing, indicates if the number of set bits is odd or even in the binary representation of the ...

of an input cannot be decided by any AC⁰ circuits, even with non-uniformity. It follows that AC⁰ is not equal to NC¹, because a family of circuits in the latter class can compute parity. More precise bounds follow from switching lemma. Using them, it has been shown that there is an oracle separation between the

polynomial hierarchy In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. ...

and PSPACE.

References

{{ComplexityClasses Circuit complexity Complexity classes