We present the first natural \NP-complete problem whose average-case hardness w.r.t. the uniform distribution over instances is \emph{equivalent} to the existence of one-way functions (OWFs). The problem, which originated in the 1960s, is the \emph{Conditional Time-Bounded Kolmogorov Complexity Problem}: let K^t(x \mid 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[\zeta] be the set of strings (x,z,k) where |z| = \zeta(|x|), |k| = \log |x| and K^t(x \mid z)< k, where, for our purposes, a ``program'' is defined as a RAM machine.
Our main result shows that for every polynomial t(n)\geq n^2, there exists some polynomial \zeta such that \mcktp[\zeta] is \NP-complete. We additionally extend the result of Liu-Pass (FOCS'20) to show that for every
polynomial t(n)\geq 1.1n, and every polynomial \zeta(\cdot), mild average-case hardness of \mcktp[\zeta] 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 \not \subseteq \BPP:
\emph{There exists concrete polynomials t,\zeta such that ``Basing OWFs on \NP \not \subseteq \BPP'' is equivalent to providing a ``worst-case to (mild) average-case reduction for \mcktp[\zeta]''.}
In other words, the ``holy-grail'' of Cryptography (i.e., basing OWFs on \NP \not\subseteq \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 \emph{polynomial-time bounded symmetry of information} assertion (Kolmogorov'68).
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 K^t(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[t,\zeta] be the set of strings (x,z,k) where |z| = \zeta(|x|), |k| = \log |x| and K^t(x | z)< k, where, for our purposes, a ``program'' is defined as a RAM machine.
Our main results shows that for every polynomial t(n)\geq n^2, there exists some polynomial \zeta such that McKTP[t,\zeta] is NP-complete. We additionally extend the result of Liu-Pass (FOCS'20) to show that for every
polynomial t(n)\geq 1.1n, and every polynomial \zeta(\cdot), mild average-case hardness of McKTP[t,\zeta] is equivalent to the existence of OWFs.
We present the first natural \NP-complete problem whose average-case hardness w.r.t. the uniform distribution over instances implies the existence of one-way functions (OWF). In fact, we prove that the existence of OWFs is \emph{equivalent} to mild average-case hardness of this \NP-complete problem. The problem, which originated in the 1960s, is the \emph{Conditional Time-Bounded Kolmogorov Complexity Problem}: let K^t(x \mid 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[t,\zeta] be the set of strings (x,z,k) where |z| = \zeta(|x|), |k| = \log |x| and K^t(x \mid z)< k, where, for our purposes, a ``program'' is defined as a RAM machine.
Our main results shows that for every polynomial t(n)\geq n^2, there exists some polynomial \zeta such that \mcktp[t,\zeta] is \NP-complete. We additionally observe that the result of Liu-Pass (FOCS'20) extends to show that for every polynomial t(n)\geq 1.1n, and every polynomial \zeta(\cdot), mild average-case hardness of \mcktp[t,\zeta] is equivalent to the existence of OWFs.
