Paper 2003/187
Resource Bounded Unprovability of Computational Lower Bounds
Tatsuaki Okamoto and Ryo Kashima
Abstract
This paper introduces new notions of asymptotic proofs, PT(polynomial-time)-extensions, PTM(polynomial-time Turing machine)--consistency, etc. on formal theories of arithmetic including PA (Peano Arithmetic). An asymptotic proof is a set of infinitely many formal proofs, which is introduced to define and characterize a property, PTM--consistency, of a formal theory. Informally speaking, PTM--consistency is a {\it polynomial-time bounded} version (in asymptotic proofs) of -consistency, and characterized in two manners: (1) (in the light of the {\it extension of PTM to TM}) the resource {\it unbounded} version of PTM--consistency is equivalent to -consistency, and (2) (in the light of {\it asymptotic proofs by PTM})
a PTM--{\it inconsistent} theory includes an axiom that only a super-polynomial-time Turing machine can prove asymptotically over PA, under some assumptions. This paper shows that {\it PNP (more generally, any super-polynomial-time lower bound in PSPACE) is unprovable in a PTM--consistent theory }, where is a consistent PT-extension of PA (although this paper does not show that PNP is unprovable in PA, since PA has not been proven to be PTM--consistent). This result implies that to prove PNP by any technique requires a PTM--{\it inconsistent} theory, which should include an axiom that only a super-polynomial-time machine can prove asymptotically over PA (or implies a super-polynomial-time computational upper bound) under some assumptions. This result is a kind of generalization of the result of ``Natural Proofs'' by Razborov and Rudich, who showed that to prove ``PNP'' by a class of techniques called ``Natural Proofs'' implies a super-polynomial-time (e.g., sub-exponential-time) algorithm that can break a typical cryptographic primitive, a pseudo-random generator. Our result also implies that any relativizable proof of PNP requires the {\it resource unbounded version} of \PTM--{\it inconsistent} theory, -{\it inconsistent} theory, which suggests another negative result by Baker, Gill and Solovay that no relativizable proof can prove ``PNP'' in PA, which is a -consistent theory.
Therefore, our result gives a unified view to the existing two major negative results on proving PNP, Natural Proofs and relativizable proofs, through the two manners of characterization of PTM--consistency. We also show that the PTM--consistency of cannot be proven in any PTM--consistent theory , where is a consistent PT-extension of . That is, to prove the independence of P vs NP from by proving the PTM--consistency of requires a PTM--{\it inconsistent} theory, or implies a super-polynomial-time computational upper bound under some assumptions. This seems to be related to the results of Ben-David and Halevi and Kurz, O'Donnell and Royer, who showed that to prove the independence of P vs NP from PA using any currently known mathematical paradigm implies an extremely-close-to-polynomial-time (but still super-polynomial-time) algorithm that can solve NP-complete problems. Based on this result, we show that {\it the security of any computational cryptographic scheme is unprovable} in the setting where adversaries and provers are modeled as polynomial-time Turing machines and only a PTM--consistent theory is allowed to prove the security.