ACC (complexity)
Encyclopedia
ACC0, sometimes called ACC, is a class of computational models and problems defined in circuit complexity
, a field of theoretical computer science. The class is defined as by augmenting the class AC0
of "alternating circuits" with the ability to count; the acronym ACC stands for "AC with counters". Specifically, a problem belongs ACC0 if it can be solved by polynomial-size, constant-depth circuits of unbounded fan-in gates, including gates that count modulo a fixed integer. ACC0 corresponds to computation in any solvable monoid
. 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.
More formally, a language belongs to AC0[m] if it can be computed by a family of circuits C1, C2, ..., where Cn takes n inputs, the depth of every circuit is constant, the size of Cn is a polynomial function of n, and the circuit uses the following gates: AND gate
s and OR gate
s of unbounded fan-in
, 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 ACC0 if it belongs to AC0[m] for some m.
In some texts, ACCi refers to a hierarchy of circuit classes with ACC0 at its lowest level, where the circuits in ACCi have depth O
(login) and polynomial size.
The class ACC0 can also be defined in terms of computations of nonuniform deterministic finite automata (NUDFA) over monoid
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 ACC0 is the family of languages accepted by a NUDFA over some monoid that does not contain an unsolvable group
as a subsemigroup.
. This inclusion is strict, because a single MOD-2 gate computes the parity function, which is known to be impossible in AC0. More generally, the function MODm can not be computed in AC0[p] for prime p unless m is a power of p.
Every problem in ACC0 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 class ACC0 is included in TC0
.
A 2010 manuscript of Ryan Williams
shows that ACC0 does not contain NEXPTIME
. The proof bases on many results in complexity theory, including time hierarchy theorem
, IP = PSPACE
, derandomization, ideas in proof of Toda's theorem
.
It is known that computing the permanent
is impossible for logspace-uniform ACC0 circuits, which implies that the complexity class PP
is not contained in logspace-uniform ACC0.
It is conjectured that ACC0 is unable to compute the majority function
of its inputs, but this remains unresolved as of 2010.
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....
, a field of theoretical computer science. The class is defined as by augmenting the class AC0
AC0
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 and polynomial size, with unlimited-fanin AND gates and OR gates....
of "alternating circuits" with the ability to count; the acronym ACC stands for "AC with counters". Specifically, a problem belongs ACC0 if it can be solved by polynomial-size, constant-depth circuits of unbounded fan-in gates, including gates that count modulo a fixed integer. ACC0 corresponds to computation in any solvable monoid
Monoid
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...
. 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, ACC0 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 AC0[m] if it can be computed by a family of circuits C1, C2, ..., where Cn takes n inputs, the depth of every circuit is constant, the size of Cn is a polynomial function of n, and the circuit uses the following gates: 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 of unbounded fan-in
Fan-In
Fan-in is the number of inputs of an electronic logic gate. For instance the fan-in for the AND gate shown below is 3. Physical logic gates with a large fan-in tend to be slower than those with a small fan-in, because the complexity of the input circuitry increases the input capacitance of the...
, 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 ACC0 if it belongs to AC0[m] for some m.
In some texts, ACCi refers to a hierarchy of circuit classes with ACC0 at its lowest level, where the circuits in ACCi have depth O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(login) and polynomial size.
The class ACC0 can also be defined in terms of computations of nonuniform deterministic finite automata (NUDFA) over monoid
Monoid
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...
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 ACC0 is the family of languages accepted by a NUDFA over some monoid that does not contain an unsolvable group
Solvable group
In mathematics, more specifically in the field of group theory, a solvable group is a group that can be constructed from abelian groups using extensions...
as a subsemigroup.
Computational power
The class ACC0 includes AC0AC0
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 and polynomial size, with unlimited-fanin AND gates and OR gates....
. This inclusion is strict, because a single MOD-2 gate computes the parity function, which is known to be impossible in AC0. More generally, the function MODm can not be computed in AC0[p] for prime p unless m is a power of p.
Every problem in ACC0 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 class ACC0 is included in TC0
TC0
TC0 is a complexity class used in circuit complexity. It is the first class in the hierarchy of TC classes.TC0 contains all languages which are decided by Boolean circuits with constant depth and polynomial size, containing only unbounded-fanin AND gates, OR gates, and majority gates...
.
A 2010 manuscript of Ryan Williams
Ryan Williams (computer scientist)
Richard Ryan Williams is an American computer scientist working in computational complexity theory.-Education:Williams received his Ph.D in computer science in 2007 from Carnegie Mellon University under the supervision of Manuel Blum. As of 2010, he is a member of the Theory Group of IBM Almaden...
shows that ACC0 does not contain NEXPTIME
NEXPTIME
In computational complexity theory, the complexity class NEXPTIME is the set of decision problems that can be solved by a non-deterministic Turing machine using time O for some polynomial p, and unlimited space....
. The proof bases on many results in complexity theory, including time hierarchy theorem
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...
, IP = PSPACE
IP (complexity)
In computational complexity theory, the class IP is the class of problems solvable by an interactive proof system. The concept of an interactive proof system was first introduced by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in 1985...
, derandomization, ideas in proof of Toda's theorem
Toda's theorem
Toda's theorem 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. The theorem states that the entire polynomial hierarchy PH is contained in PPP; this implies a closely related statement, that PH is contained in P#P...
.
It is known that computing the permanent
Computing the permanent
In mathematics, the computation of the permanent of a matrix is a problem that is believed to be more complex than the computation of the determinant of a matrix despite the apparent similarity of the definitions....
is impossible for logspace-uniform ACC0 circuits, which implies that the complexity class PP
PP (complexity)
In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time...
is not contained in logspace-uniform ACC0.
It is conjectured that ACC0 is unable to compute the majority function
Majority function
In Boolean logic, the majority function is a function from n inputs to one output. The value of the operation is false when n/2 or more arguments are false, and true otherwise....
of its inputs, but this remains unresolved as of 2010.