Resource Bounded Unprovability of Computational Lower Bounds

Tatsuaki Okamoto, Ryo Kashima

This paper introduces new notions of asymptotic proofs, PT(polynomial-time)-extensions, PTM(polynomial-time Turing machine)-omega-consistency, etc. on formal theories of arithmetic…