Mathematical Logic Quarterly 52 (6):613-624 (2006)

Authors
Abstract
We prove that the sharply bounded arithmetic T02 in a language containing the function symbol ⌊x /2y⌋ is equivalent to PV1
Keywords sharply bounded formula  polynomial‐time function  Bounded arithmetic
Categories (categorize this paper)
DOI 10.1002/malq.200610019
Options
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: 60,949
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Bounded Arithmetic and the Polynomial Hierarchy.Jan Krajíček, Pavel Pudlák & Gaisi Takeuti - 1991 - Annals of Pure and Applied Logic 52 (1-2):143-153.
Relating the Bounded Arithmetic and Polynomial Time Hierarchies.Samuel R. Buss - 1995 - Annals of Pure and Applied Logic 75 (1-2):67-77.
A Note on Sharply Bounded Arithmetic.Jan Johannsen - 1994 - Archive for Mathematical Logic 33 (2):159-165.

Add more references

Citations of this work BETA

Approximate Counting in Bounded Arithmetic.Emil Jeřábek - 2007 - Journal of Symbolic Logic 72 (3):959 - 993.
Approximate Counting by Hashing in Bounded Arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.

View all 11 citations / Add more citations

Similar books and articles

A Remark on Independence Results for Sharply Bounded Arithmetic.Jan Johannsen - 1998 - Mathematical Logic Quarterly 44 (4):568-570.
Approximate Counting by Hashing in Bounded Arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
Preservation Theorems for Bounded Formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.
Notes on Polynomially Bounded Arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
A Note on Sharply Bounded Arithmetic.Jan Johannsen - 1994 - Archive for Mathematical Logic 33 (2):159-165.
Herbrand Consistency of Some Arithmetical Theories.Saeed Salehi - 2012 - Journal of Symbolic Logic 77 (3):807-827.
Two General Results on Intuitionistic Bounded Theories.Fernando Ferreira - 1999 - Mathematical Logic Quarterly 45 (3):399-407.
Polynomially Bounded Recursive Realizability.Saeed Salehi - 2005 - Notre Dame Journal of Formal Logic 46 (4):407-417.

Analytics

Added to PP index
2013-12-01

Total views
24 ( #445,820 of 2,439,389 )

Recent downloads (6 months)
1 ( #433,984 of 2,439,389 )

How can I increase my downloads?

Downloads

My notes