On proofs about threshold circuits and counting hierarchies
Jan Johannsen, Chris Pollett · 2002
We define theories of Bounded Arithmetic characterizing classes of functions computable by constant-depth 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 so-called RSUV-isomorphism.