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 the Boolean circuits that compute them. A related notion is the circui ...

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

hierarchy. Each class, ACⁱ, consists of the languages 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 input ...

s with depth

O(\log^i n)

and a polynomial number of unlimited fan-in

AND or AND may refer to: Logic, grammar, and computing * Conjunction (grammar), connecting two words, phrases, or clauses * Logical conjunction in mathematical logic, notated as "∧", "⋅", "&", or simple juxtaposition * Bitwise AND, a boolea ...

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

s. 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 machine In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP. ...

s., page 27-18. The smallest AC class is AC⁰, consisting of constant-depth unlimited fan-in circuits. The total hierarchy of AC classes is defined as

$\mbox = \bigcup_ \mbox^i$

Relation to NC

The AC classes are related to the NC classes, which are defined similarly, but with gates having only constant fanin. For each ''i'', we have :

\mbox^i \subseteq \mbox^i \subseteq \mbox^.

As an immediate consequence of this, we have that NC = AC. It is known that inclusion is strict for ''i'' = 0.

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, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation). Given two positive numbers and , modulo (often abbreviated as ) is th ...

for some modulus ''m'', we have the classes ACCⁱ

Notes

References

* * *. * {{ComplexityClasses Circuit complexity Complexity classes