A feasible theory for analysis

Journal of Symbolic Logic 59 (3):1001-1011 (1994)

Authors
Abstract
We construct a weak second-order theory of arithmetic which includes Weak König's Lemma (WKL) for trees defined by bounded formulae. The provably total functions (with Σ b 1 -graphs) of this theory are the polynomial time computable functions. It is shown that the first-order strength of this version of WKL is exactly that of the scheme of collection for bounded formulae
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2275924
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


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

References found in this work BETA

Factorization of Polynomials and °1 Induction.S. G. Simpson - 1986 - Annals of Pure and Applied Logic 31 (2):289.

Add more references

Citations of this work BETA

Bounded Functional Interpretation.Fernando Ferreira & Paulo Oliva - 2005 - Annals of Pure and Applied Logic 135 (1):73-112.
Number Theory and Elementary Arithmetic.Jeremy Avigad - 2003 - Philosophia Mathematica 11 (3):257-284.
Forcing in Proof Theory.Jeremy Avigad - 2004 - Bulletin of Symbolic Logic 10 (3):305-333.

View all 16 citations / Add more citations

Similar books and articles

Analytics

Added to PP index
2009-01-28

Total views
268 ( #23,115 of 2,266,401 )

Recent downloads (6 months)
24 ( #33,095 of 2,266,401 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature