International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Ryo Kashima

Publications

Year
Venue
Title
2003
EPRINT
Resource Bounded Unprovability of Computational Lower Bounds
Tatsuaki Okamoto Ryo Kashima
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.

Coauthors

Tatsuaki Okamoto (1)