6
$\begingroup$

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.
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ Sep 25, 2023 at 10:24
  • $\begingroup$ 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. $\endgroup$
    – agemO
    Sep 25, 2023 at 11:57

1 Answer 1

8
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ "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. $\endgroup$
    – agemO
    Sep 26, 2023 at 20:20
  • $\begingroup$ 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)? $\endgroup$
    – agemO
    Sep 26, 2023 at 20:38
  • $\begingroup$ "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. $\endgroup$
    – agemO
    Sep 27, 2023 at 7:27
  • 2
    $\begingroup$ In answer to the question in the 2nd comment above: Yes, it's believed that all of these measures are hard to compute. $\endgroup$ Sep 28, 2023 at 14:35
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 11, 2023 at 9:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.