TR97-016 Authors: Manindra Agrawal, Eric Allender, Samir Datta

Publication: 5th May 1997 09:28

Downloads: 974

Keywords:

Continuing a line of investigation that has studied the

function classes #P, #SAC^1, #L, and #NC^1, we study the

class of functions #AC^0. One way to define #AC^0 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 no nontrivial lower bounds, lower

bounds for #AC^0 follow easily from established circuit lower

bounds.

One of our main results is a characterization of TC^0 in

terms of #AC^0: A language A is in TC^0 if and only if there

is a #AC^0 function f and a number k such that x \in A \iff

f(x) = 2^{|x|^k}. Using well known naming conventions

this yields: TC^0 = PAC^0 = C_=AC^0.

Another restatement of this characterization is that TC^0 can

be simulated by constant-depth arithmetic circuits, with a

single threshold gate. We hope that perhaps this

characterization of TC^0 in terms of AC^0 circuits might

provide a new avenue of attack for proving lower bounds.

Our characterization differs markedly from earlier

characterizations of TC^0 in terms of arithmetic circuits

over finite fields Using our model of arithmetic circuits,

computation over finite fields yields ACC^0.

We also prove a number of closure properties and normal forms

for #AC^0.