Welcome to the resource topic for 2003/187
Title:
Resource Bounded Unprovability of Computational Lower Bounds
Authors: Tatsuaki Okamoto, 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.
ePrint: https://eprint.iacr.org/2003/187
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .