Computational Power
The class ACC0 includes AC0. This inclusion is strict, because a single MOD-2 gate computes the parity function, which is known to be impossible to compute in AC0. More generally, the function MODm can not be computed in AC0 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.
Ryan Williams announced in 2010 and published in 2011 a proof that ACC0 does not contain NEXPTIME. The proof uses many results in complexity theory, including the time hierarchy theorem, IP = PSPACE, derandomization, and ideas in the 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 July 2012.
Read more about this topic: ACC0
Famous quotes containing the word power:
“Cruelty is a mystery, and the waste of pain. But if we describe a word to compass these things, a world that is a long, brute game, then we bump against another mystery: the inrush of power and delight, the canary that sings on the skull.”
—Annie Dillard (b. 1945)