Abstract
Continuing a line of investigation that has studied the function classes P, we study the class of functions AC/sup 0/. One way to define AC/sup 0/ is as the class of functions computed by constant-depth polynomial-size arithmetic circuits of unbounded fanin addition and multiplication gates. In contrast to the preceding function classes, for which we know no nontrivial lower bounds, lower bounds for AC/sup 0/ follow easily from established circuit lower bounds. One of our main results is a characterization of TC/sup 0/ in terms of AC/sup 0/: A language A is in TC/sup 0/ if and only if there is a AC/sup 0/ function f and a number k such that x/spl isin/A/spl hArr/f(x)=2/sup |x|k/. Using the naming conventions, this yields: TC/sup 0/=PAC/sup 0/=C=AC/sup 0/. Another restatement of this characterization is that TC/sup 0/ can be simulated by constant-depth arithmetic circuits, with a single threshold gate. We hope that perhaps this characterization of TC/sup 0/ in terms of AC/sup 0/ circuits might provide a new avenue of attack for proving lower bounds. Our characterization differs markedly from earlier characterizations of TC/sup 0/ in terms of arithmetic circuits over finite fields. Using our model of arithmetic circuits, computation over finite fields yields ACC/sup 0/. We also prove a number of closure properties and normal forms for AC/sup 0/.