NP Search Problems in Low Fragments of Bounded Arithmetic

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

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}$

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,261

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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.
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
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
2010-08-24

Downloads
26 (#614,101)

6 months
1 (#1,478,781)

Historical graph of downloads
How can I increase my downloads?