Let subexp denote the class of all monotonic functions that are bounded above by some constructible function f such that, for any d > 0, f ( n ) = o ( 2 nd ). Let subsubexp denote any class of monotonic functions closed under composition with polynomials such that, for any two functions f and g in the class, the composition of f and g is in subexp.
A typical example of a function in subexp is 2 n 1 &slash; log * n, and a typical function in subsubexp is
2 ( log n ) O ( loglog n ) .
A language L is said to be in ACC if and only if there exists a positive integer m such that L is recognized by a family of constant-depth polynomial-size circuits containing NOT gates and unbounded fan-in AND, OR, and MODm gates. The authors’ main result is that the permanent function does not have ACC(subexp) circuits. They leave the question of whether uniformity is necessary in their proof unanswered. The results they prove about the permanent do not rely on any unproven complexity-theoretic assumptions. In particular, their result is in contrast to results that prove stronger intractability results about the permanent under the hypothesis that the polynomial hierarchy is infinite.
