User:Thore Husfeldt/sandbox

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

ACC⁰ Circuits

Informally, ACC⁰ 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 C₁, C₂, … belongs AC⁰(m) if 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- 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 ACC⁰ if it belongs to AC⁰(m) for some m.

Relations to other Complexity Classes

The class ACC⁰ includes AC⁰. This inclusion is strict, because a single MOD2-gate computes the parity function, which is known to be impossible in AC⁰. More generally, the function MODm can not be computed in AC⁰(p) for prime p unless m is a power of p.

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 class ACC⁰ is included in TC⁰.

A 2010 manuscript Ryan Williams shows that ACC⁰ does not contain NEXP.

References

• Circuit Complexity before the Dawn of the New Millennium, a 1997 survey of the field by Eric Allender

Category:Computational complexity theory

Graph coloring
Problem
Input	Graph $G$ with $n$ vertices. Integer $k$
Output	Does $G$ admit a proper vertex coloring with $k$ colors?
Algorithms
Running time	$O(2^{n}n)$
Complexity	NP-complete
Garey–Johnson	GT4

Chromatic number
Problem
Input	Graph $G$ with $n$ vertices.
Output	$\chi (G)$
Algorithms
Running time	$O(2^{n}n)$
Complexity	NP-hard
Garey–Johnson	GT4
Approximable	$O(n(\log n)^{-3}(\log \log n)^{2})$
Not approximable	$n^{1-\epsilon }$ unless P=NP

Chromatic polynomial
Problem
Input	Graph $G$ with $n$ vertices. Integer $k$
Output	The number $P(G,k)$ of proper $k$-colorings of $G$
Algorithms
Running time	$O(2^{n}n)$
Complexity	#P-complete
Approximable	FPRAS for restricted cases
Not approximable	No PTAS unless P=NP

Graph coloring
Decision problem
Input	Graph coloring
Input	Graph $G$ with $n$ vertices. Integer $k$
Output	Does $G$ admit a proper vertex coloring with $k$ colors?
Running time	$O(2^{n}n)$
Complexity	NP-complete
Reduction from	3-Satisfiability
Garey–Johnson	GT4
Optimisation problem
Name	Chromatic number
Input	Graph $G$ with $n$ vertices.
Output	$\chi (G)$
Running time	$O(2^{n}n)$
Complexity	NP-hard
Approximable	$O(n(\log n)^{-3}(\log \log n)^{2})$
Not approximable	$n^{1-\epsilon }$ unless P=NP
Counting problem
Name	Chromatic polymomial
Input	Graph $G$ with $n$ vertices. Integer $k$
Output	The number $P(G,k)$ of proper $k$-colorings of $G$
Running time	$O(2^{n}n)$
Complexity	#P-complete
Approximable	FPRAS for restricted cases
Not approximable	No PTAS unless P=NP

Petersen graph
The Petersen graph is most commonly drawn as a pentagon with a pentagram inside, with five spokes.
Named after	Julius Petersen
Vertices	10
Edges	15
Radius	2
Diameter	2
Girth	5
Chromatic number	3
Chromatic index	$(k-2)(k-1)k(k^{7}-12k^{6}+67k^{5}-230k^{4}+520k^{3}-814k^{2}+775k-352)$
Properties	Cubic Strongly regular Snark
Table of graphs and parameters