The provably total NP search problems of weak second order bounded arithmetic

Annals of Pure and Applied Logic 162 (6):419-446 (2011)
  Copy   BIBTEX


We define a new NP search problem, the “local improvement” principle, about labellings of an acyclic, bounded-degree graph. We show that, provably in , it characterizes the consequences of and that natural restrictions of it characterize the consequences of and of the bounded arithmetic hierarchy. We also show that over V0 it characterizes the consequences of V1 and hence that, in some sense, a miniaturized version of the principle gives a new characterization of the consequences of . Throughout our search problems are “type-2” NP search problems, which take second-order objects as parameters



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

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

A feasible theory for analysis.Fernando Ferreira - 1994 - Journal of Symbolic Logic 59 (3):1001-1011.
Provably total functions of intuitionistic bounded arithmetic.Victor Harnik - 1992 - Journal of Symbolic Logic 57 (2):466-477.
On interpretations of bounded arithmetic and bounded set theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.
Regularity in models of arithmetic.George Mills & Jeff Paris - 1984 - Journal of Symbolic Logic 49 (1):272-280.
Approximate counting by hashing in bounded arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
Groundwork for weak analysis.António M. Fernandes & Fernando Ferreira - 2002 - Journal of Symbolic Logic 67 (2):557-578.
Parallel strategies.Pavel Pudlák - 2003 - Journal of Symbolic Logic 68 (4):1242-1250.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Approximate Counting in Bounded Arithmetic.Emil Jeřábek - 2007 - Journal of Symbolic Logic 72 (3):959 - 993.


Added to PP

21 (#757,947)

6 months
9 (#352,458)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Phuong Nguyen
University of Georgia

Citations of this work

Incompleteness in the Finite Domain.Pavel Pudlák - 2017 - Bulletin of Symbolic Logic 23 (4):405-441.
The canonical pairs of bounded depth Frege systems.Pavel Pudlák - 2021 - Annals of Pure and Applied Logic 172 (2):102892.

Add more citations