✦ LIBER ✦
Polynomial induction and length minimization in intuitionistic bounded arithmetic
✍ Scribed by Morteza Moniri
- Publisher
- John Wiley and Sons
- Year
- 2005
- Tongue
- English
- Weight
- 80 KB
- Volume
- 51
- Category
- Article
- ISSN
- 0044-3050
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
It is shown that the feasibly constructive arithmetic theory IPV does not prove (double negation of) LMIN(NP), unless the polynomial hierarchy CPV‐provably collapses. It is proved that PV plus (double negation of) LMIN(NP) intuitionistically proves PIND(coNP). It is observed that PV + PIND(NP ∪ coNP) does not intuitionistically prove NPB, a scheme which states that the extended Frege systems are not polynomially bounded. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)