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:
“I have seen in this revolution a circular motion of the sovereign power through two usurpers, father and son, to the late King to this his son. For ... it moved from King Charles I to the Long Parliament; from thence to the Rump; from the Rump to Oliver Cromwell; and then back again from Richard Cromwell to the Rump; then to the Long Parliament; and thence to King Charles, where long may it remain.”
—Thomas Hobbes (1579–1688)