Paper 2024/687 Original: eprint.iacr.org/2024/687 ↗

Lower Bounds for Levin–Kolmogorov Complexity

Abstract

The hardness of Kolmogorov complexity is intricately connected to the existence of one-way functions and derandomization. An important and elegant notion is Levin's version of Kolmogorov complexity, \(\mathsf{Kt}\), and its decisional variant, \(\mathsf{MKtP}\). The question whether \(\mathsf{MKtP}\) can be computed in polynomial time is particularly interesting because it is not subject to known technical barriers such as algebrization or natural proofs that would explain the lack of a proof for \(\mathsf{MKtP} \not\in \mathsf{P}\). We take a major step towards proving \(\mathsf{MKtP} \not\in \mathsf{P}\) by developing a novel yet simple diagonalization technique to show unconditionally that \(\mathsf{MKtP} \not \in \mathsf{DTIME}[O(n)]\), i.e., no deterministic linear-time algorithm can solve \(\mathsf{MKtP}\) on every instance. This allows us to affirm a conjecture by Ren and Santhanam [STACS:RS22] about a non-halting variant of \(\mathsf{Kt}\) complexity. Additionally, we give conditional lower bounds for \(\mathsf{MKtP}\) that tolerate either more runtime or one-sided error. If the underlying computational model has a linear-time universal simulation, e.g.\ random-access machines, then we obtain a quadratic lower bound, i.e., \(\mathsf{MKtP} \not\in \mathsf{DTIME}[O(n^2)]\).