Arithmetic Versions of Constant Depth Circuit Complexity Classes
Hubie Chen · 2001
The boolean circuit complexity classes AC0 AC0[m] TC0 NC1 have been studied in-tensely. Other than NC1, 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 AC0[m], while the other classes AC0[m] as well as TC0 lack such technology. Continuing a line of research originating from Valiant’s work on the counting class]P, the arithmetic circuit complexity classes]AC0 and]NC1 have recently been studied. In this paper, we define and investigate the classes]AC0[m] and]TC0. Just as the boolean classes AC0[m] and TC0 give a refined view of NC1, our new arithmetic classes, which fall into the inclusion chain]AC0 ]AC0[m] ]TC0 ]NC1, refine]NC1. These new classes (along with]AC0) are also defined by constant-depth circuits, but the allowed gates compute arithmetic functions. We also introduce the classes DiffAC0[m] (differences of two AC0[m] functions), which generalize the class DiffAC0 studied in previous work. We study the structure of three hierarchies: the]AC0[m] hierarchy, the DiffAC0[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]AC0[m] has exactly the same structure as the hierarchy of classes AC0[m]: AC0[m] AC0[m0] iff]AC0[m] ]AC0[m0] We also investigate closure properties of our new classes, which generalize those appearing in previ-ous work on]AC0 and DiffAC0.