Abstract:
Constant-depth arithmetic circuits have been defined and studied in [AAD97,ABL98]; these circuits yield the function classes #AC^0 and GapAC^0. These function classes in turn provide new characterizations of the computational power of threshold circuits, and provide a link between the circuit classes AC^0 (where many lower bounds are known) and TC^0 (where essentially no lower bounds are known). In this paper, we resolve several questions regarding the closure properties of #AC^0 and GapAC^0. Counting classes are usually characterized in terms of problems of counting paths in a class of graphs (simple paths in directed or undirected graphs for #P, simple paths in directed acyclic graphs for #L, or paths in bounded-width graphs for GapNC^1). It was shown in [BLMS98] that complete problems for depth k Boolean AC^0 can be obtained by considering the reachability problem for width $k$ grid graphs. It would be tempting to conjecture that #AC^0 could be characterized by counting paths in bounded-width grid graphs. We disprove this, but nonetheless succeed in characterizing #AC^0 by counting paths in another family of bounded-width graphs.