Levin–Kolmogorov Complexity is not in Linear Time

ePrint Report: Levin–Kolmogorov Complexity is not in Linear Time

Nicholas Brandt

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 …

complexity computational connections eprint report functions important linear notion question report search theory understanding version