Fast algorithms for time bounded Kolmogorov complexity

Question

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|)$.

1. Efficiently computable variants of Kolmogorov complexity
2. Kolmogorov complexity with weak description languages
3. Sipser, M. (1983). A complexity theoretic approach to randomness. Proceedings of the fifteenth annual ACM symposium on Theory of computing.
4. Lu, Z., Oliveira, I.C., & Zimand, M. (2022). Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. ArXiv, abs/2204.08312.
5. Bauwens, B., Makhlin, A., Vereshchagin, N.K., & Zimand, M. (2013). Short lists with short programs in short time. computational complexity, 27, 31-61.
6. Oliveira I.C. (2019). Randomness and intractability in Kolmogorov complexity.

Answer 1

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