期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1997
卷号：1997
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
