Constant-depth arithmetic circuits ahve 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 lowr 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 and characterize # AC~0 in erms of counting paths in a family of bounded-width graphs.
展开▼
