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, \(Kt\) , and its decisional variant, \(\textsf{MKtP}\) . The question whether \(\textsf{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 \(\textsf{MKtP}\not \in \textsf{P}\) . We take a major step towards proving \(\textsf{MKtP}\not \in \textsf{P}\) by developing a novel yet simple diagonalization technique to show unconditionally that \(\textsf{MKtP}\not \in \textsf{DTIME}\left[ \mathcal {O}\left( n\right) \right] \) , i.e., no deterministic linear-time algorithm can solve \(\textsf{MKtP}\) on every instance. This allows us to affirm a conjecture by Ren and Santhanam [64] about a non-halting variant of \(Kt\) complexity. Additionally, we give conditional lower bounds for \(\textsf{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., \(\textsf{MKtP}\not \in \textsf{DTIME}\left[ \mathcal {O}\left( n^2\right) \right] \) .