Hardness Along the Boundary: Towards One-Way Functions from the Worst-Case Hardness of Time-Bounded Kolmogorov Complexity

We consider the question of whether worst-case hardness of the time-bounded Kolmogorov complexity problem, $\KpolyA$---that is, determining whether a string is time-bounded Kolmogorov random ($K^t$-random) or not---suffices to imply the existence of one-way functions (OWF).

Roughly speaking, our main result shows that under a natural strengthening of standard-type derandomization assumptions, worst-case hardness of the boundary version of this classic problem characterizes OWFs.

In more detail, let $\bKtA$ denote the problem of, given an instance $x$, deciding whether (a) $K^{t_2}(x)\geq n-1$, or (b) $K^{t_1}(x) < n-1$ but $K^{t_2}> n - \log n$; that is, deciding whether $x$ is $K^t$-random, or just ``near" $K^t$-random. We say that $\bKpolyA \notin \ioBPP$ if $\bKpolyA \notin \ioBPP$ for all polynomials $t_1,t_2$.

We show that under a natural strengthening of standard derandomization assumptions (namely, there exists a constant $\varepsilon > 0$ such that $\E \not\subseteq {\sf ioNTIME}[2^{kn}] \slash 2^{\varepsilon n}$ for every $k \in \N$), OWF exist iff $\bKpolyA \notin \ioBPP$. Along the way, we also demonstrate that if we consider the probabilistic version of Kolmogorov complexity (referred to as $pK^t$) instead, then the characterization holds unconditionally.

We finally observe that for most standard optimization problems, hardness along boundary" is equivalent to plain" worst-case hardness, indicating that assuming hardness along the boundary may be WLOG.