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(polynomialtime)extensions, PTM(polynomialtime 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 polynomialtime 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 superpolynomialtime Turing machine can prove asymptotically over PA, under some assumptions. This paper shows that {\it P$\not=$NP (more generally, any superpolynomialtime lower bound in PSPACE) is unprovable in a PTM$\omega$consistent theory $T$}, where $T$ is a consistent PTextension 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 superpolynomialtime machine can prove asymptotically over PA (or implies a superpolynomialtime 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 superpolynomialtime (e.g., subexponentialtime) algorithm that can break a typical cryptographic primitive, a pseudorandom 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 PTextension 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 superpolynomialtime computational upper bound under some assumptions. This seems to be related to the results of BenDavid 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 extremelyclosetopolynomialtime (but still superpolynomialtime) algorithm that can solve NPcomplete 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 polynomialtime Turing machines and only a PTM$\omega$consistent theory is allowed to prove the security.
Metadata
 Available format(s)
 PDF PS
 Category
 Foundations
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 computational complexitycomputational lower boundP vs NPnatural proofscryptographyunprovabilityundecidabilityproof theoryincompleteness theorem
 Contact author(s)
 okamoto @ isl ntt co jp
 History
 20050106: last of 2 revisions
 20030910: received
 See all versions
 Short URL
 https://ia.cr/2003/187
 License

CC BY
BibTeX
@misc{cryptoeprint:2003/187, author = {Tatsuaki Okamoto and Ryo Kashima}, title = {Resource Bounded Unprovability of Computational Lower Bounds}, howpublished = {Cryptology ePrint Archive, Paper 2003/187}, year = {2003}, note = {\url{https://eprint.iacr.org/2003/187}}, url = {https://eprint.iacr.org/2003/187} }