Paper 2024/687
Levin–Kolmogorov Complexity is not in Linear Time
, ETH ZurichAbstract
Understanding the computational hardness of Kolmogorov complexity is a central open question in complexity theory. An important notion is Levin's version of Kolmogorov complexity, Kt, and its decisional variant, MKtP, due to its connections to universal search, derandomization, and oneway functions, among others. 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 not in P. We take a significant step towards proving MKtP not in P by developing an algorithmic approach for showing unconditionally that MKtP not in DTIME[O(n)] cannot be decided in deterministic linear time in the worst-case. This allows us to partially affirm a conjecture by Ren and Santhanam [STACS:RS22] 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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Kolmogorov complexitylower bound
- Contact author(s)
- nicholas brandt @ inf ethz ch
- History
- 2024-05-06: approved
- 2024-05-05: received
- See all versions
- Short URL
- https://ia.cr/2024/687
- License
-
CC BY-SA
BibTeX
@misc{cryptoeprint:2024/687,
author = {Nicholas Brandt},
title = {Levin–Kolmogorov Complexity is not in Linear Time},
howpublished = {Cryptology ePrint Archive, Paper 2024/687},
year = {2024},
note = {\url{https://eprint.iacr.org/2024/687}},
url = {https://eprint.iacr.org/2024/687}
}
