DocumentCode
1958736
Title
On proofs about threshold circuits and counting hierarchies
Author
Johannsen, Jan ; Pollett, Chris
Author_Institution
Dept. of Math., California Univ., San Diego, La Jolla, CA, USA
fYear
1998
fDate
21-24 Jun 1998
Firstpage
444
Lastpage
452
Abstract
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
Keywords
computational complexity; threshold logic; Bounded Arithmetic; RSUV-isomorphism; constant-depth threshold circuits; counting hierarchies; threshold circuits; Algebra; Circuit simulation; Complexity theory; Computer science; Digital arithmetic; Mathematics; Polynomials;
fLanguage
English
Publisher
ieee
Conference_Titel
Logic in Computer Science, 1998. Proceedings. Thirteenth Annual IEEE Symposium on
Conference_Location
Indianapolis, IN
ISSN
1043-6871
Print_ISBN
0-8186-8506-9
Type
conf
DOI
10.1109/LICS.1998.705678
Filename
705678
Link To Document