6

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.
agemO
  • 187
  • 4
  • 2
    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. – Marzio De Biasi Sep 25 '23 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. – agemO Sep 25 '23 at 11:57

1 Answers1

8

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

agemO
  • 187
  • 4
Eric Allender
  • 1,871
  • 21
  • 16
  • "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" I think the reason why it could be easier is exactly because such short descriptions would be discarded. – agemO Sep 26 '23 at 20:20
  • 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)? – agemO Sep 26 '23 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. – agemO Sep 27 '23 at 07:27
  • 2
    In answer to the question in the 2nd comment above: Yes, it's believed that all of these measures are hard to compute. – Eric Allender Sep 28 '23 at 14:35
  • I added your comment as an edit to the answer itself, I'll accept it once the edit is accepted. – agemO Oct 02 '23 at 09:52
  • Is there some action taht you're requesting from me? I don't know how to "accept" an edit... – Eric Allender Oct 06 '23 at 19:37
  • Someone accepted it, thanks for the answer! – agemO Oct 08 '23 at 18:31
  • I don't know if it is worth a separate question but in the end is there any known non trivial class of restricted programs for which the (correspondingly bounded) Kolmogorov complexity (or the inverse problem itself) is tractable? In the literature, there is one cluster about hard theoretical complexity or even meta complexity questions, and another one about very simple learning algorithms such as "how L2 regularization is a simplicity bias for linear regression?", but I have a hard time finding anything in between. – agemO Oct 10 '23 at 07:23
  • 1
    I believe that there isn't any "non trivial class of restricted programs" for which the correspondingly bounded K-complexity problem is tractable. The "trivial" classes would consist of any class of functions that are guaranteed to be easy to invert (such as, for instance, restricting the universal Turing machine U to be logspace-bounded and to have one-way access to the description d, where U(d) = x. But I don't think that this class of functions would give a very useful notion of Kolmogorov complexity. – Eric Allender Oct 11 '23 at 09:20