Journal of Symbolic Logic 72 (2):649 - 672 (2007)

Abstract
We give combinatorial and computational characterizations of the NP search problems definable in the bounded arithmetic theories $T_{2}^{2}$ and $T_{3}^{2}$
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2178/jsl/1185803628
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: 64,262
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

No references found.

Add more references

Citations of this work BETA

Conservative Fragments of {{S}^{1} {2}} and {{R}^{1} {2}}.Chris Pollett - 2011 - Archive for Mathematical Logic 50 (3-4):367-393.

View all 9 citations / Add more citations

Similar books and articles

Notes on Polynomially Bounded Arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Tautologies From Pseudo-Random Generators.Jan Krajíček - 2001 - Bulletin of Symbolic Logic 7 (2):197-212.
On Interpretations of Bounded Arithmetic and Bounded Set Theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.
Fragments of Bounded Arithmetic and the Lengths of Proofs.Pavel Pudl'ak - 2008 - Journal of Symbolic Logic 73 (4):1389-1406.
Regularity in Models of Arithmetic.George Mills & Jeff Paris - 1984 - Journal of Symbolic Logic 49 (1):272-280.
On the Restraining Power of Guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.

Analytics

Added to PP index
2010-08-24

Total views
24 ( #457,816 of 2,455,764 )

Recent downloads (6 months)
1 ( #449,201 of 2,455,764 )

How can I increase my downloads?

Downloads

My notes