“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 7734
School of Mathematics
  Title:   Polynomial induction and length minimization in intuitionistic bounded arithmetic
  Author(s):  Mor. Moniri
  Status:   Published
  Journal: Math. Logic Quart.
  Vol.:  51
  Year:  2005
  Pages:   73-76
  Supported by:  IPM
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 sates that the extended Frege systems are not polynomially bounded.

Download TeX format
back to top
scroll left or right