ACC0 - Definitions

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 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 gates and OR gates 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 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 monoids. 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.

Read more about this topic:  ACC0

Famous quotes containing the word definitions:

    “Lord Byron is an exceedingly interesting person, and as such is it not to be regretted that he is a slave to the vilest and most vulgar prejudices, and as mad as the winds?
    There have been many definitions of beauty in art. What is it? Beauty is what the untrained eyes consider abominable.”
    —Edmond De Goncourt (1822–1896)

    “What I do not like about our definitions of genius is that there is in them nothing of the day of judgment, nothing of resounding through eternity and nothing of the footsteps of the Almighty.”
    —G.C. (Georg Christoph)