Mathematical Logic Quarterly 48 (2):221-243 (2002)

In this paper we provide a new arithmetic characterization of the levels of the og-time hierarchy . We define arithmetic classes equation image and equation image that correspond to equation image-LOGTIME and equation image-LOGTIME, respectively. We break equation image and equation image into natural hierarchies of subclasses equation image and equation image. We then define bounded arithmetic deduction systems equation image′ whose equation image-definable functions are precisely B. We show these theories are quite strong in that LIOpen proves for any fixed m that equation image, TAC, a theory that is slightly stronger than equation image′ whose equation image-definable functions are LH, proves LH is not equal to equation image-TIME for any m> 0, where 2s ∈L, s ∈ ω, and TAC proves LH ≠ equation image for all k and m. We then show that the theory TAC cannot prove the collapse of the polynomial hierarchy. Thus any such proof, if it exists, must be argued in a stronger systems than ours
Keywords bounded arithmetic  feasible ower bounds  independence
Categories (categorize this paper)
DOI 10.1002/1521-3870(200202)48:2
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 63,206
Through your library

References found in this work BETA

Structure and Definability in General Bounded Arithmetic Theories.Chris Pollett - 1999 - Annals of Pure and Applied Logic 100 (1-3):189-245.
Multifunction Algebras and the Provability of PH↓.Chris Pollett - 2000 - Annals of Pure and Applied Logic 104 (1-3):279-303.
Translating IΔ0 + Exp Proofs Into Weaker Systems.Chris Pollett - 2000 - Mathematical Logic Quarterly 46 (2):249-256.

Add more references

Citations of this work BETA

A Theory for Log-Space and NLIN Versus Co-NLIN.Chris Pollett - 2003 - Journal of Symbolic Logic 68 (4):1082-1090.

Add more citations

Similar books and articles

Strict $${\pi^1_1}$$ -Reflection in Bounded Arithmetic.António M. Fernandes - 2010 - Archive for Mathematical Logic 49 (1):17-34.
A Remark on Independence Results for Sharply Bounded Arithmetic.Jan Johannsen - 1998 - Mathematical Logic Quarterly 44 (4):568-570.
An Independence Result on Weak Second Order Bounded Arithmetic.Satoru Kuroda - 2001 - Mathematical Logic Quarterly 47 (2):183-186.
Notes on Polynomially Bounded Arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
On Interpretations of Bounded Arithmetic and Bounded Set Theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.
Approximate Counting by Hashing in Bounded Arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
A Note on Sharply Bounded Arithmetic.Jan Johannsen - 1994 - Archive for Mathematical Logic 33 (2):159-165.
A Theory for Log-Space and NLIN Versus Co-NLIN.Chris Pollett - 2003 - Journal of Symbolic Logic 68 (4):1082-1090.
Regularity in Models of Arithmetic.George Mills & Jeff Paris - 1984 - Journal of Symbolic Logic 49 (1):272-280.


Added to PP index

Total views
19 ( #560,138 of 2,448,343 )

Recent downloads (6 months)
1 ( #450,727 of 2,448,343 )

How can I increase my downloads?


My notes