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

Categories

Keywords

Reprint years

DOI

10.2178/jsl/1185803628

Other Versions

No versions found

Links

PhilArchive

External links

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

Through your library

My notes

Similar books and articles

Approximate counting and NP search problems.Leszek Aleksander Kołodziejczyk & Neil Thapen - 2022 - Journal of Mathematical Logic 22 (3).
The provably total NP search problems of weak second order bounded arithmetic.Leszek Aleksander Kołodziejczyk, Phuong Nguyen & Neil Thapen - 2011 - Annals of Pure and Applied Logic 162 (6):419-446.
Witnessing functions in bounded arithmetic and search problems.Mario Chiari & Jan Krajíček - 1998 - Journal of Symbolic Logic 63 (3):1095-1115.
Herbrandizing search problems in Bounded Arithmetic.Jiří Hanika - 2004 - Mathematical Logic Quarterly 50 (6):577-586.
Nested PLS.Toshiyasu Arai - 2011 - Archive for Mathematical Logic 50 (3-4):395-409.
Fragments of bounded arithmetic and the lengths of proofs.Pavel Pudl'ak - 2008 - Journal of Symbolic Logic 73 (4):1389-1406.
Preservation theorems for bounded formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.
Characterising Definable Search Problems in Bounded Arithmetic via Proof Notations.Arnold Beckmann & Samuel R. Buss - 2010 - In Ralf Schindler, Ways of Proof Theory. Berlin, Boston: De Gruyter. pp. 65-134.
Tautologies from pseudo-random generators.Jan Krajíček - 2001 - Bulletin of Symbolic Logic 7 (2):197-212.
Jan Krajíček, Pavel Pudlák, and Gaisi Takeuti. Bounded arithmetic and the polynomial hierarchy. Ibid., vol. 52, pp. 143–153. - Samuel R. Buss. Relating the bounded arithmetic and polynomial time hierarchies. Ibid., vol. 75, pp. 67–77. - Domenico Zambella. Notes on polynomially bounded arithmetic. The journal of symbolic logic, vol. 61, pp. 942–966.Stephen Cook - 1999 - Journal of Symbolic Logic 64 (4):1821-1823.

Analytics

Added to PP
2010-08-24

Downloads
98 (#528,692)

6 months
23 (#457,824)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

View all 11 citations / Add more citations

References found in this work

No references found.

Add more references