Resource Bounded Unprovability of Computational Lower Bounds
<|reference_start|>Resource Bounded Unprovability of Computational Lower Bounds: 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 including PA (Peano Arithmetic). This paper shows that P not= NP (more generally, any super-polynomial-time lower bound in PSPACE) is unprovable in a PTM-omega-consistent theory T, where T is a consistent PT-extension of PA. This result gives a unified view to the existing two major negative results on proving P not= NP, Natural Proofs and relativizable proofs, through the two manners of characterization of PTM-omega-consistency. We also show that the PTM-omega-consistency of T cannot be proven in any PTM-omega-consistent theory S, where S is a consistent PT-extension of T.<|reference_end|>
@article{okamoto2005resource,
    title={Resource Bounded Unprovability of Computational Lower Bounds},
    author={Tatsuaki Okamoto, Ryo Kashima},
    journal={arXiv preprint arXiv:cs/0503091},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0503091},
    primaryClass={cs.CC cs.LO}
}