“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 7734  


Abstract:  
It is shown that the feasibly constructive arithmetic theory IPV
does not prove (double negation of) LMIN(NP), unless the
polynomial hierarchy CPVprovably 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 