Paper 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)]\).

Note: This version fixes an inefficiency that was overlooked in the first version. Namely, an additive term of log(n) (for the global compression notion) that makes the results more robust against the underlying machine model. Additionally, a density argument for 1-random strings now allows for some false-positive error.