On TC0, AC(0), and arithmetic circuits

Continuing a line of investigation that has studied the function classes #P , #SAC(1), #L, and #NC1, we study the class of functions #AC(0). One way to define #AC(0) is as the class of functions computed by constant-depth poly nomial-size arithmetic circuits of unbounded fan-in addition and multiplica tion gates. In contrast to the preceding function classes, for which we kno w to nontrivial lower bounds, lower bounds for #AC(0) follow easily from es tablished circuit lower bounds. One of our main results is a characterizati on of TC0 in terms of #AC(0): A language A is in TC0 if and only if there i s a #AC(0) function f and a number k such that x epsilon A double left righ t arrow f(x) = 2(\x\k). Using the naming conventions of Fenner et al. r1994 , J. Comput. System Sci. 48, 116-148) and Caussinus et al. (1998, J. Comput . System Sci. 57, 200-212), this yields differs markedly from earlier chara cterizations of TC0 in terms in arithmatic circuits over finite fields. Usi ng our model of arithmatic circuits, computation over finite fields yields ACC(0). We also prove a number of clousure properties and normal forms for #AC(0). (C) 2000 Academic Press.