文章基本信息

标题：Bounded Depth Arithmetic Circuits: Counting and Closure
本地全文：下载
作者：Eric Allender ; Andris Ambainis ; David Mix Barrington 等
期刊名称：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.
关键词：arithmetic circuits, Counting Circuits, Threshold Circuits