__
TR01-095 | 12th November 2001 00:00
__

#### Arithmetic Versions of Constant Depth Circuit Complexity Classes

TR01-095
Authors:

Hubie Chen
Publication: 5th December 2001 06:36

Downloads: 1603

Keywords:

**Abstract:**
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

technology.

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.