On TC⁰, AC⁰, and arithmetic circuits

Abstract

Continuing a line of investigation that has studied the function classes #P, #SAC¹, #L, and #NC¹, we study the class of functions #AC⁰. One way to define #AC⁰ is as the class of functions computed by constant-depth polynomial-size arithmetic circuits of unbounded fan-in addition and multiplication gates. In contrast to the preceding function classes, for which we know to nontrivial lower bounds, lower bounds for #AC⁰ follow easily from established circuit lower bounds. One of our main results is a characterization of TC⁰ in terms of #AC⁰: a language A is in TC⁰ if and only if there is a #AC⁰ function f and a number k such that x∈A⇔f(x)=2^|x|k. Using the naming conventions of Fenner et al. (1994, J. Comput. System Sci.48, 116-148) and Caussinus et al. (1998, J. Comput. System Sci.57, 200-212), this yields TC⁰=PAC⁰=C₌AC⁰. Another restatement of this characterization is that TC⁰ can be simulated by constant-depth arithmetic circuits, with a single threshold gate. We hope that perhaps this characterization of TC⁰ in terms of AC⁰ circuits might provide a new avenue of attack for proving lower bounds. Our characterization differs markedly from earlier characterizations of TC⁰ in terms of arithmetic circuits over finite fields. Using our model of arithmetic circuits, computation over finite fields yields ACC⁰. We also prove a number of closure properties and normal forms for #AC⁰.