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)-$\omega$-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-$\omega$-consistency, of a formal theory. Informally speaking, PTM-$\omega$-consistency is a {\it polynomial-time bounded} version (in asymptotic proofs) of $\omega$-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-$\omega$-consistency is equivalent to $\omega$-consistency, and (2) (in the light of {\it asymptotic proofs by PTM}) a PTM-$\omega$-{\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 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 (although this paper does not show that P$\not=$NP is unprovable in PA, since PA has not been proven to be PTM-$\omega$-consistent). This result implies that to prove P$\not=$NP by any technique requires a PTM-$\omega$-{\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 ``P$\not=$NP'' 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 P$\not=$NP requires the {\it resource unbounded version} of \PTM-$\omega$-{\it inconsistent} theory, $\omega$-{\it inconsistent} theory, which suggests another negative result by Baker, Gill and Solovay that no relativizable proof can prove ``P$\not=$NP'' in PA, which is a $\omega$-consistent theory. Therefore, our 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$. That is, to prove the independence of P vs NP from $T$ by proving the PTM-$\omega$-consistency of $T$ requires a PTM-$\omega$-{\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-$\omega$-consistent theory is allowed to prove the security.