Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR01-095 | 12th November 2001 00:00

Arithmetic Versions of Constant Depth Circuit Complexity Classes


Authors: Hubie Chen
Publication: 5th December 2001 06:36
Downloads: 3847


The boolean circuit complexity classes
AC^0 \subseteq AC^0[m] \subseteq TC^0 \subseteq NC^1 have been studied
intensely. Other than NC^1, they are defined by constant-depth
circuits of polynomial size and unbounded fan-in over some set of
allowed gates. One reason for interest in these classes is that they
contain the boundary marking the limits of current lower bound
technology: such technology exists for AC^0 and some of the classes
AC^0[m], while the other classes AC^0[m] as well as TC^0 lack such

Continuing a line of research originating from Valiant's work on the
counting class #P, the arithmetic circuit complexity classes #AC^0 and
#NC^1 have recently been studied. In this paper, we define and
investigate the classes #AC^0[m] and #TC^0. Just as the boolean
classes AC^0[m] and TC^0 give a refined view of NC^1, our new
arithmetic classes, which fall into the inclusion chain
#AC^0 \subseteq #AC^0[m] \subseteq #TC^0 \subseteq #NC^1, refine
#NC^1. These new classes (along with #AC^0) are also defined by
constant-depth circuits, but the allowed gates compute arithmetic
functions. We also introduce the classes DiffAC^0[m] (differences of
two AC^0[m] functions), which generalize the class DiffAC^0 studied in
previous work.

We study the structure of three hierarchies: the #AC^0[m] hierarchy,
the DiffAC^0[m] hierarchy, and a hierarchy of language classes. We
prove class separations and containments where possible, and
demonstrate relationships among the various hierarchies. For
instance, we prove that the hierarchy of classes #AC^0[m] has
exactly the same structure as the hierarchy of classes AC^0[m]:

AC^0[m] \subseteq AC^0[m'] iff #AC^0[m] \subseteq #AC^0[m']

We also investigate closure properties of our new classes, which
generalize those appearing in previous work on #AC^0 and DiffAC^0.

ISSN 1433-8092 | Imprint