ACC0

Sketch of an ACC-circuit: For a fixed number m, the circuit consists of NOT-, AND-, OR-, and (Mod m)-Gates. The fan-in of each gate is bounded by a polynomial and the depth of the circuit is bounded by a constant.

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 by augmenting the class AC0 of constant-depth "alternating circuits" with the ability to count; the acronym ACC stands for "AC with counters".[1] Specifically, a problem belongs to 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.

  1. ^ Vollmer (1999), p. 126