Jump to content

User:Thore Husfeldt/sandbox

From Wikipedia, the free encyclopedia

ACC0, sometimes called ACC, is a class of computational models and problems defined in circuit complexity, a field of theoretical computer science. A problem belongs ACC0 if it can be solved by polynomial-size, constant-depth circuits of unbounded fan-in gates, including "counting" gates. ACC0 corresponds to computation in any solvable algebra. 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.

ACC0 Circuits

[edit]

Informally, ACC0 models the class of computations realised by Boolean circuits of constant depth and polynomial size, where the circuit gates includes “counting gates” that compute the number of true inputs modulo some fixed constant.


More formally, an infinite family of circuits C1, C2, … belongs AC0(m) if 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- 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 MODm-gates, which compute 1 if the number of input 1s is a multiple of m. A circuit family belongs to ACC0 if it belongs to AC0(m) for some m.


Relations to other Complexity Classes

[edit]

The class ACC0 includes AC0. This inclusion is strict, because a single MOD2-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 Ryan Williams shows that ACC0 does not contain NEXP.

References

[edit]


Category:Computational complexity theory


Graph coloring

Problem
InputGraph with vertices. Integer
OutputDoes admit a proper vertex coloring with colors?
Algorithms
Running time
ComplexityNP-complete
Garey–JohnsonGT4


Chromatic number
Problem
InputGraph with vertices.
Output
Algorithms
Running time
ComplexityNP-hard
Garey–JohnsonGT4
Approximable
Not approximable unless P=NP
Chromatic polynomial
Problem
InputGraph with vertices. Integer
OutputThe number of proper -colorings of
Algorithms
Running time
Complexity#P-complete
ApproximableFPRAS for restricted cases
Not approximableNo PTAS unless P=NP
Graph coloring

Decision problem
InputGraph coloring
InputGraph with vertices. Integer
OutputDoes admit a proper vertex coloring with colors?
Running time
ComplexityNP-complete
Reduction from3-Satisfiability
Garey–JohnsonGT4
Optimisation problem
NameChromatic number
InputGraph with vertices.
Output
Running time
ComplexityNP-hard
Approximable
Not approximable unless P=NP
Counting problem
NameChromatic polymomial
InputGraph with vertices. Integer
OutputThe number of proper -colorings of
Running time
Complexity#P-complete
ApproximableFPRAS for restricted cases
Not approximableNo PTAS unless P=NP
Petersen graph
The Petersen graph is most commonly drawn as a pentagon with a pentagram inside, with five spokes.
Named afterJulius Petersen
Vertices10
Edges15
Radius2
Diameter2
Girth5
Chromatic number3
Chromatic index
PropertiesCubic
Strongly regular
Snark
Table of graphs and parameters