# Fast algorithms for time bounded Kolmogorov complexity

For a universal Turing machine $$U$$, the time bounded Kolmogorov complexity of a string $$x$$ is silmilar to the usual Kolmogorov complexity but limited to programs $$p$$ running in time at most $$t(|x|)$$: $$K^t(x) = \min_{p} \{ |p| \: : \: \mathcal{U}(p) \text{ outputs } x \text{ in less than } t(|x|) \text{ steps} \}$$

What are the fastest known algorithms to compute $$K^t(x)$$ (or even find the corresponding shortest programs $$p$$)?
Particularly, what about polynomial complexity $$t$$ (a.k.a. $$K^{poly}$$) or even low degree polynomial such as $$t = O(|x|)$$ or $$t = O(|x|^2)$$?

There are tons of related questions and literature, but I can't find any actual algorithm or time complexity bounds beyond the usual brut force enumeration and execution of all programs $$p$$ smaller than $$|x|$$ (which might never halt in the unbounded setting).

There are two other related time bounded Kolmogorov complexity definitions [6]:

$$K_t(x) = \min_{p} \{ |p| + \log{t} \: : \: \mathcal{U}(p) \text{ outputs } x \text{ in } t \text{ steps} \}$$

$$KT(x) = \min_{p} \{ |p| + t \: : \: \mathcal{U}(p) \text{ outputs } x \text{ in } t \text{ steps} \}$$

For which we have no proof yet that it is not computable in polynomial time (but we do know that the randomized version $$rK_t$$ cannot be estimated in $$BPP$$).

A possible alternate definition I've never encountered is one where the time bound is a function of $$|p|$$ instead of $$|x|$$:

$$K^{t^{\prime}}(x) = \min_{p} \{ |p| \: : \: \mathcal{U}(p) \text{ outputs } x \text{ in less than } t^{\prime}(|p|) \text{ steps} \}$$

It seems to me that some long running time programs $$p$$ are allowed by the $$K^t$$ definition but forbidden by the $$K^{t^{\prime}}$$ one, so that $$K^{t^{\prime}}$$ might happen to be faster to compute.
For example, for i in 2^1000 print("1") would be a valid candidate for a linear $$t(|x|)$$ but not for a linear $$t(|p|)$$.

• Note that there is a strong connection with the P vs NP (guess $p$ and verify it in polynomial time); so I think there is no hope for time bounds of $K^t(x)$ other than brute force. Commented Sep 25, 2023 at 10:24
• That is also my gut feeling about $K^t$ but I can't find any exact statement about it. For $K^{t^{\prime}}$ I have no idea. Commented Sep 25, 2023 at 11:57

TL;DR: It is believed that no polynomial time algorithm exists for neither $$K_t$$, $$K^{poly}$$ nor $$KT$$.
We have no idea about $$K^{t^{\prime}}$$ since it has never really been studied.
No faster algorithm is known for computing $$K_t(x)$$ than the brute-force algorithm. In fact, since the (average-case) complexity of computing $$K_t(x)$$ is closely tied to the existence of one-way functions (see [Liu & Pass, FOCS 2020]) many of us think that it is extremely unlikely that anything significantly better than a brute-force approach will arise. Certainly any better algorithm would be VERY interesting.
You are right that the measure $$K^{t^{\prime}}$$ that you describe would be easier to compute. I can't think of any setting where people have found that it would be interesting to investigate. But it's possible. (But you might need to investigate some conventions that would allow you to "describe" the entire string $$x$$ with a running time that is much less than the length of $$x$$, if the description is very short. The measure $$KT$$ that I've studied provides one such convention. I've written a survey that you might find relevant: https://people.cs.rutgers.edu/~allender/papers/jones.pdf
• By the way nice survey, do I understand correctly that not only $K_t$ but also $K^{poly}$, and $KT$ are all believed to be hard to compute (i.e. there would be no polynomial time algorithm to compute them)? Commented Sep 26, 2023 at 20:38
• "can't think of any setting where people have found that it would be interesting to investigate $K^{t^{\prime}}$" -> When I first read the natural language description of $K^{t}$ the first thing that came to my mind was in fact $K^{t^{\prime}}$, probably because I'm mainly interested in learning theory so that I have no hope for practical algorithms if we allow exponential expansion (from $|p|$ to $|x|$) to happen. Commented Sep 27, 2023 at 7:27