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:
“By the power elite, we refer to those political, economic, and military circles which as an intricate set of overlapping cliques share decisions having at least national consequences. In so far as national events are decided, the power elite are those who decide them.”
—C. Wright Mills (1916–1962)