ACC0 - Computational Power

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 MOD_m 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.