Title: First Order Bounded Arithmetic and Small Boolean Circuit Complexity Classes
Abstract: A well known result of proof theory is the characterization of primitive recursive functions ƒ as those provably recursive in the first order theory of Peano arithmetic with the induction axiom restricted to Σ1 formulas. In this paper, we study a variety of weak theories of first order arithmetic, whose provably total functions (with graphs of a certain form) are exactly those computable within some resource bound on a particular computation model (boolean circuits, with possible parity or MOD 6 gates, or threshold circuits, or alternating Turing machines, or ordinary Turing machines). To establish these kinds of results for small complexity classes, we provide a recursion-theoretic characterization of the complexity class, prove how one can encode sequences in very weak theories, and use the witnessing technique of [7].
Publication Year: 1995
Publication Date: 1995-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 55
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot