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

Authors
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
Keywords Kripke model  IPV  length minimization  extended Frege system  polynomial induction
Categories (categorize this paper)
DOI 10.1002/malq.200410008
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: 52,704
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

Preservation Theorems for Bounded Formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.

Add more citations

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.
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-6):643-660.
Notes on Polynomially Bounded Arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
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 index
2013-12-01

Total views
12 ( #724,604 of 2,340,047 )

Recent downloads (6 months)
1 ( #516,585 of 2,340,047 )

How can I increase my downloads?

Downloads

My notes