ACC⁰, sometimes called ACC, is a class of computational models and problems defined in

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

, a field of theoretical computer science. The class is defined by augmenting the class AC⁰ of constant-depth "alternating circuits" with the ability to count; the acronym ACC stands for "AC with counters"., p. 126 Specifically, a problem belongs to ACC⁰ if it can be solved by polynomial-size, constant-depth circuits of unbounded fan-in gates, including gates that count modulo a fixed integer. ACC⁰ corresponds to computation in any solvable

monoid In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoids ...

. The class is very well studied in theoretical computer science because of the algebraic connections and because it is one of the largest concrete computational models for which computational impossibility results, so-called circuit lower bounds, can be proved.

Definitions

Informally, ACC⁰ models the class of computations realised by Boolean circuits of constant depth and polynomial size, where the circuit gates includes "modular counting gates" that compute the number of true inputs modulo some fixed constant. More formally, a language belongs to AC⁰ 'm''if it can be computed by a family of circuits ''C''₁, ''C''₂, ..., where ''C_n'' takes ''n'' inputs, the depth of every circuit is constant, the size of ''C_n'' is a polynomial function of ''n'', and the circuit uses the following gates:

AND gate The AND gate is a basic digital logic gate that implements logical conjunction (∧) from mathematical logic AND gate behaves according to the truth table. A HIGH output (1) results only if all the inputs to the AND gate are HIGH (1). If not all ...

s 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 lev ...

s of unbounded

fan-in Fan-in is the number of inputs a logic gate can handle. For instance the fan-in for the AND gate shown in the figure is 3. Physical logic gates with a large fan-in tend to be slower than those with a small fan-in. This is because the complexity ...

, computing the conjunction and disjunction of their inputs; NOT gates computing the negation of their single input; and unbounded fan-in MOD-''m'' gates, which compute 1 if the number of input 1s is a multiple of ''m''. A language belongs to ACC⁰ if it belongs to AC⁰ 'm''for some ''m''. In some texts, ACC^''i'' refers to a hierarchy of circuit classes with ACC⁰ at its lowest level, where the circuits in ACC^''i'' have depth O(log^''i''''n'') and polynomial size. The class ACC⁰ can also be defined in terms of computations of nonuniform deterministic finite automata (NUDFA) over

s. In this framework, the input is interpreted as elements from a fixed monoid, and the input is accepted if the product of the input elements belongs to a given list of monoid elements. The class ACC⁰ is the family of languages accepted by a NUDFA over some monoid that does not contain an unsolvable group as a subsemigroup.

Computational power

The class ACC⁰ includes AC⁰. This inclusion is strict, because a single MOD-2 gate computes the parity function, which is known to be impossible to compute in AC⁰. More generally, the function MOD_''m'' cannot be computed in AC⁰ 'p''for prime ''p'' unless ''m'' is a power of ''p''. The class ACC⁰ is included in TC⁰. It is conjectured that ACC⁰ is unable to compute the

majority function In Boolean logic, the majority function (also called the median operator) is the Boolean function that evaluates to false when half or more arguments are false and true otherwise, i.e. the value of the function equals the value of the majority of th ...

of its inputs (i.e. the inclusion in TC⁰ is strict), but this remains unresolved as of July 2018. Every problem in ACC⁰ can be solved by circuits of depth 2, with AND gates of polylogarithmic fan-in at the inputs, connected to a single gate computing a symmetric function. These circuits are called SYM⁺-circuits. The proof follows ideas of the proof of

Toda's theorem Toda's theorem is a result in computational complexity theory that was proven by Seinosuke Toda in his paper "PP is as Hard as the Polynomial-Time Hierarchy" and was given the 1998 Gödel Prize. Statement The theorem states that the entire poly ...

. proves that ACC⁰ does not contain

NEXPTIME In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time 2^. In terms of NTIME, :\mathsf = \bigcup_ \mathsf(2^) A ...

. The proof uses many results in complexity theory, including the

time hierarchy theorem In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, ...

, IP = PSPACE,

derandomization A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...

, and the representation of ACC⁰ via SYM⁺ circuits. improves this bound and proves that ACC⁰ does not contain NQP (nondeterministic quasipolynomial time). It is known that computing the permanent is impossible for LOGTIME-uniform ACC⁰ circuits, which implies that the complexity class PP is not contained in LOGTIME-uniform ACC⁰.

Notes

References

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