On Proofs About Threshold Circuits and Counting Hierarchies (Extended Abstract)
Jan Johannsen, Chris Pollett · 1998
) Jan Johannsen Chris Pollett Department of Mathematics Department of Computer Science University of California, San Diego Boston University La Jolla, CA 91093-0112 Boston, MA 02215 Abstract We define theories of Bounded Arithmetic characterizing classes of functions computable by constantdepth threshold circuits of polynomial and quasipolynomial size. Then we define certain second-order theories and show that they characterize the functions in the Counting Hierarchy. Finally we show that the former theories are isomorphic to the latter via the socalled RSUV -isomorphism. 1 Introduction A phenomenon that is commonly observed in Complexity Theory is that proofs of results about counting complexity classes (#P , Mod p P etc.) can often be scaled down to yield results about small depth circuit classes with the corresponding counting gates. For example, Toda's result [17] that every problem in the Polynomial Hierarchy can be solved in polynomial time with an oracle for #P correspon...