Welcome to the resource topic for 2024/687
Title:
Levin–Kolmogorov Complexity is not in Linear Time
Authors: Nicholas Brandt
Abstract: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.
ePrint: https://eprint.iacr.org/2024/687
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .