AC0
Encyclopedia
AC0 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 gate
s and OR gate
s. (We allow NOT gates only at the inputs). It thus contains NC0, which has only bounded-fanin AND and OR gates.
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 operator, or alternatively by FO(+,
), or by Turing machine in the logarithmic hierarchy
.
In 1984 Furst, Saxe, and Sipser showed that calculating the parity
of an input cannot be decided by any AC0 circuits, even with non-uniformity.
It follows that AC0 is not equal to NC1, because a family of circuits in the latter class can compute parity.
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
used in circuit complexity
Circuit complexity
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them....
. It is the smallest class in the AC
AC (complexity)
In circuit complexity, AC is a complexity class hierarchy. Each class, ACi, consists of the languages recognized by Boolean circuits with depth O and a polynomial number of unlimited-fanin AND and OR gates....
hierarchy, and consists of all families of circuits of depth O(1) and polynomial size, with unlimited-fanin AND gate
AND gate
The AND gate is a basic digital logic gate that implements logical conjunction - it behaves according to the truth table to the right. A HIGH output results only if both the inputs to the AND gate are HIGH . If neither or only one input to the AND gate is HIGH, a LOW output results...
s and OR gate
OR gate
The OR gate is a digital logic gate that implements logical disjunction - it behaves according to the truth table to the right. A HIGH output results if one or both the inputs to the gate are HIGH . If neither input is HIGH, a LOW output results...
s. (We allow NOT gates only at the inputs). It thus contains NC0, which has only bounded-fanin AND and OR gates.
From a descriptive complexity
Descriptive complexity
Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For example, PH, the union of all complexity classes in the polynomial hierarchy, is precisely the...
viewpoint, DLOGTIME
DLOGTIME
DLOGTIME is the complexity class of all computational problems solvable in a logarithmic amount of computation time on a deterministic Turing machine. It is the smallest nontrivial class using the resource of deterministic time...
-uniform AC0 is equal to the descriptive class FO
FO (complexity)
FO is the complexity class of structures which can be recognised by formulae of first-order logic. It is the foundation of the field of descriptive complexity and is equal to the complexity class AC0 FO-regular...
+BIT of all languages describable in first-order logic with the addition of the BIT operator, or alternatively by FO(+,
), or by Turing machine in the logarithmic hierarchyLH (complexity)
Logarithmic Hierarchy is the complexity class of all computational problems solvable in a logarithmic amount of computation time on an alternating Turing machine with a bounded number of alternation. It is a special case of hierarchy of bounded alternating Turing machine...
.
In 1984 Furst, Saxe, and Sipser showed that calculating the parity
Parity function
In Boolean algebra, a parity function is a Boolean function whose value is 1 if the input vector has an odd number of ones.The parity function is notable for its role in theoretical investigation of circuit complexity of Boolean functions.-Definition:...
of an input cannot be decided by any AC0 circuits, even with non-uniformity.
It follows that AC0 is not equal to NC1, because a family of circuits in the latter class can compute parity.