Resource Bounded Unprovability of Computational Lower Bounds
| dc.creator | Okamoto, Tatsuaki | |
| dc.creator | Kashima, Ryo | |
| dc.date | 2005-03-31 | |
| dc.date.accessioned | 2026-07-07T03:22:47Z | |
| dc.date.available | 2026-07-07T03:22:47Z | |
| dc.description | 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. | |
| dc.description | 78 pages | |
| dc.identifier | https://arxiv.org/abs/cs/0503091 | |
| dc.identifier | http://arxiv.org/abs/cs/0503091 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/32689 | |
| dc.subject | Computational Complexity | |
| dc.subject | Logic in Computer Science | |
| dc.subject | F.1.3; F.4.1; F.2.2 | |
| dc.title | Resource Bounded Unprovability of Computational Lower Bounds | |
| dc.type | text |