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.

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
2005-01-06: last of 2 revisions
2003-09-10: received
See all versions
Short URL
https://ia.cr/2003/187
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.