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