HOME

TheInfoList



OR:

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, ACi, 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 O(\log^i n) 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
\mbox = \bigcup_ \mbox^i


Relation to NC

The AC classes are related to NC, ACC, and TC classes. For each ''i'', we have, p. 437; , p. 118. :\mathsf^i \subseteq \mathsf^i \subseteq \mathsf^ \subseteq \mathsf^ \subseteq \mathsf^. As an immediate consequence of this, we have that NC = AC = ACC = TC. We have \mathsf^0 \subsetneq \mathsf^0 \subsetneq \mathsf^. Specifically, PARITY is in \mathsf^0 but not in \mathsf^0. And since NC requires bounded fan-in, any function of type \^n \to \ whose output depends on more than O(1) inputs is beyond \mathsf^0. In particular, the unbounded fan-in OR is beyond \mathsf^0. In detail, define f_n: \^n \to \ by f_n(x_1, \dots, x_n) = \sum_i x_i \mod 2 . Then it requires \Omega(2^) gates to be computed by a \mathsf^0 circuit with depth \leq d .


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