On TC0, AC0, and arithmetic circuits

Agrawal, Manindra ; Allender, Eric ; Datta, Samir (2000) On TC0, AC0, and arithmetic circuits Journal of Computer and System Sciences, 60 (2). pp. 395-421. ISSN 0022-0000

PDF - Publisher Version

Official URL: http://linkinghub.elsevier.com/retrieve/pii/S00220...

Related URL: http://dx.doi.org/10.1006/jcss.1999.1675


Continuing a line of investigation that has studied the function classes #P, #SAC1, #L, and #NC1, we study the class of functions #AC0. One way to define #AC0 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 #AC0 follow easily from established circuit lower bounds. One of our main results is a characterization of TC0 in terms of #AC0: a language A is in TC0 if and only if there is a #AC0 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 TC0=PAC0=C=AC0. Another restatement of this characterization is that TC0 can be simulated by constant-depth arithmetic circuits, with a single threshold gate. We hope that perhaps this characterization of TC0 in terms of AC0 circuits might provide a new avenue of attack for proving lower bounds. Our characterization differs markedly from earlier characterizations of TC0 in terms of arithmetic circuits over finite fields. Using our model of arithmetic circuits, computation over finite fields yields ACC0. We also prove a number of closure properties and normal forms for #AC0.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
ID Code:20220
Deposited On:20 Nov 2010 14:50
Last Modified:17 May 2016 04:36

Repository Staff Only: item control page