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

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.

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 In computational complexity theory, a unary language or tally language is a formal language (a set of strings) where all strings have the form 1''k'', where "1" can be any fixed symbol. For example, the language is unary, as is the language . The ...

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

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

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

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

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

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 In computational complexity theory, Håstad's switching lemma is a key tool for proving lower bounds on the size of constant-depth Boolean circuits. Using the switching lemma, showed that Boolean circuits of depth ''k'' in which only AND, OR, and N ...

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

References

{{ComplexityClasses Circuit complexity Complexity classes