Abstract
The class ACC consists of circuit families with constant depth over unbounded fan-in AND, OR, NOT, and MODm gates, where m > 1 is an arbitrary constant. We prove: • NTIME[2n] does not have non-uniform ACC circuits of polynomial size. The size lower bound can be strengthened to quasi-polynomials and other less natural functions. • ENP, the class of languages recognized in 2O(n) time with an NP oracle, doesn't have non-uniform ACC circuits of 2n size. The lower bound gives a size-depth tradeoff: for every d, m there is a δ > 0 such that E doesn't have depth-d ACC circuits of size 2nδ with MODm gates. Previously, it was not known whether EXP NP had depth-3 polynomial size circuits made out of only MOD 6 gates. The high-level strategy is to design faster algorithms for the circuit satisfiability problem over ACC circuits, then prove that such algorithms can be applied to obtain the above lower bounds. © 2011 IEEE.