In
circuit complexity, AC is a
complexity class
In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...
hierarchy. Each class, AC
i, consists of the
languages
Language is a structured system of communication that consists of grammar and vocabulary. It is the primary means by which humans convey meaning, both in spoken and signed forms, and may also be conveyed through writing. Human language is ch ...
recognized by
Boolean circuit
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible inpu ...
s with depth
and a
polynomial number of
unlimited fan-in AND and
OR gates.
The name "AC" was chosen by analogy to
NC, with the "A" in the name standing for "alternating" and referring both to the alternation between the AND and OR gates in the circuits and to
alternating Turing machines.
The smallest AC class is
AC0, consisting of constant-depth unlimited fan-in circuits.
The total hierarchy of AC classes is defined as
Relation to NC
The AC classes are related to
NC,
ACC, and
TC classes. For each ''i'', we have
[, p. 437; , p. 118.]
:
As an immediate consequence of this, we have that NC = AC = ACC = TC.
We have
. Specifically, PARITY is in
but not in
. And since NC requires bounded fan-in, any function of type
whose output depends on more than
inputs is beyond
. In particular, the unbounded fan-in OR is beyond
.
In detail, define
by
. Then it requires
gates to be computed by a
circuit with depth
.
Variations
The power of the AC classes can be affected by adding additional gates. If we add gates which calculate the
modulo operation
In computing and mathematics, the modulo operation returns the remainder or signed remainder of a Division (mathematics), division, after one number is divided by another, the latter being called the ''modular arithmetic, modulus'' of the operatio ...
for some modulus ''m'', we have the classes
ACCi ">
Notes
References
*
*
*
*
*.
*
{{ComplexityClasses
Circuit complexity
Complexity classes