Polynomial induction and length minimization in intuitionistic bounded arithmetic

Mathematical Logic Quarterly 51 (1):73-76 (2005)
  Copy   BIBTEX

Abstract

It is shown that the feasibly constructive arithmetic theory IPV does not prove LMIN, unless the polynomial hierarchy CPV-provably collapses. It is proved that PV plus LMIN intuitionistically proves PIND. It is observed that PV + PIND does not intuitionistically prove NPB, a scheme which states that the extended Frege systems are not polynomially bounded

Categories

Keywords

Reprint years

DOI

10.1002/malq.200410008

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,386

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

Preservation theorems for bounded formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.
On two questions about feasibly constructive arithmetic.Morteza Moniri - 2003 - Mathematical Logic Quarterly 49 (4):425.
Review: Jan Krajicek, Pavel Pudlak, Gaisi Takeuti, Bounded Arithmetic and the Polynomial Hierarchy; Samuel R. Buss, Relating the Bounded Arithmetic and Polynomial Time Hierarchies; Domenico Zambella, Notes on Polynomially Bounded Arithmetic. [REVIEW]Stephen Cook - 1999 - Journal of Symbolic Logic 64 (4):1821-1823.
The strength of sharply bounded induction.Emil Jeřábek - 2006 - Mathematical Logic Quarterly 52 (6):613-624.
Admissible closures of polynomial time computable arithmetic.Dieter Probst & Thomas Strahm - 2011 - Archive for Mathematical Logic 50 (5):643-660.
Minimum propositional proof length is NP-Hard to linearly approximate.Michael Alekhnovich, Sam Buss, Shlomo Moran & Toniann Pitassi - 2001 - Journal of Symbolic Logic 66 (1):171-191.
Induction, minimization and collection for Δ n+1 (T)–formulas.A. Fernández-Margarit & F. F. Lara-Martín - 2004 - Archive for Mathematical Logic 43 (4):505-541.
Separations of first and second order theories in bounded arithmetic.Masahiro Yasumoto - 2005 - Archive for Mathematical Logic 44 (6):685-688.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic.Arnold Beckmann & Samuel R. Buss - 2009 - Journal of Mathematical Logic 9 (1):103-138.
The strong soundness theorem for real closed fields and Hilbert’s Nullstellensatz in second order arithmetic.Nobuyuki Sakamoto & Kazuyuki Tanaka - 2004 - Archive for Mathematical Logic 43 (3):337-349.
On diophantine equations solvable in models of open induction.Margarita Otero - 1990 - Journal of Symbolic Logic 55 (2):779-786.
On different intuitionistic calculi and embeddings from int to S.Uwe Egly - 2001 - Studia Logica 69 (2):249-277.
Time polynomial in input or output.Yuri Gurevich & Saharon Shelah - 1989 - Journal of Symbolic Logic 54 (3):1083-1088.
A new "feasible" arithmetic.Stephen Bellantoni & Martin Hofmann - 2002 - Journal of Symbolic Logic 67 (1):104-116.

Analytics

Added to PP
2013-12-01

Downloads
23 (#664,515)

6 months
6 (#504,917)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

Preservation theorems for bounded formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.

Add more citations

References found in this work

No references found.

Add more references