CryptoDB
Lower Bounds for Levin–Kolmogorov Complexity
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | TCC 2024 |
| Abstract: | The hardness of Kolmogorov complexity is intricately connected to the existence of oneway functions and derandomization. An important and elegant notion is Levin’s version of Kolmogorov complexity, Kt, and its decisional variant, MKtP. The question whether 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 MKtP ∉ P. We take a major step towards proving MKtP ∉ P by developing a novel yet simple diagonalization technique to show unconditionally that MKtP ∉ DTIME[O(n)], i.e., no deterministic algorithm can solve MKtP on every instance. This allows us to affirm a conjecture by Ren and Santhanam [STACS22] about a non-halting variant of Kt complexity. Additionally, we give conditional lower bounds for MKtP that tolerate either more runtime or one-sided error. |
BibTeX
@inproceedings{tcc-2024-34743,
title={Lower Bounds for Levin–Kolmogorov Complexity},
publisher={Springer-Verlag},
author={Nicholas Brandt},
year=2024
}