ECCC-Report TR97-016https://eccc.weizmann.ac.il/report/1997/016Comments and Revisions published for TR97-016en-usMon, 05 May 1997 09:28:49 +0300
Paper TR97-016
| On TC^0, AC^0, and Arithmetic Circuits |
Manindra Agrawal,
Eric Allender,
Samir Datta
https://eccc.weizmann.ac.il/report/1997/016
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.
Mon, 05 May 1997 09:28:49 +0300https://eccc.weizmann.ac.il/report/1997/016