期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We present the first natural NP-complete problem whose average-case hardness w.r.t. the uniform distribution over instances is equivalent to the existence of one-way functions (OWFs). The problem, which originated in the 1960s, is the Conditional Time-Bounded Kolmogorov Complexity Problem: let Kt(x | z) be the length of the shortest “program” that, given the “auxiliary input” z, outputs the string x within time t(|x|), and let McKtP[ζ] be the set of strings (x, z, k) where |z| = ζ(|x|), |k| = log |x| and Kt(x | z) < k, where, for our purposes, a “program” is defined as a RAM machine. Our main result shows that for every polynomial t(n) ≥ n2 , there exists some polynomial ζ such that McKtP[ζ] is NP-complete. We additionally extend the result of Liu-Pass (FOCS’20) to show that for every polynomial t(n) ≥ 1.1n, and every polynomial ζ(·), mild average-case hardness of McKtP[ζ] is equivalent to the existence of OWFs. Taken together, these results provide the following crisp characterization of what is required to base OWFs on NP 6⊆ BPP: There exists concrete polynomials t, ζ such that “Basing OWFs on NP 6⊆ BPP” is equivalent to providing a “worst-case to (mild) average-case reduction for McKtP[ζ]”. In other words, the “holy-grail” of Cryptography (i.e., basing OWFs on NP 6⊆ BPP) is equivalent to a basic question in algorithmic information theory. As an independent contribution, we show that our NP-completeness result can be used to shed new light on the feasibility of the polynomial-time bounded symmetry of information assertion (Kolmogorov’68).
