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