<p>TL;DR: It is believed that no polynomial time algorithm exists for neither <span class="math-container">$K_t$</span>, <span class="math-container">$K^{poly}$</span> nor <span class="math-container">$KT$</span>.<br />
We have no idea about <span class="math-container">$K^{t^{\prime}}$</span> since it has never really been studied.</p>
<p>No faster algorithm is known for computing <span class="math-container">$K_t(x)$</span> than the brute-force algorithm. In fact, since the (average-case) complexity of computing <span class="math-container">$K_t(x)$</span> is closely tied to the existence of one-way functions (see [Liu &amp; 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.</p>
<p>You are right that the measure <span class="math-container">$K^{t^{\prime}}$</span> 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 &quot;describe&quot; the entire string <span class="math-container">$x$</span> with a running time that is much less than the length of <span class="math-container">$x$</span>, if the description is very short. The measure <span class="math-container">$KT$</span> that I've studied provides one such convention. I've written a survey that you might find relevant: <a href="https://people.cs.rutgers.edu/%7Eallender/papers/jones.pdf" rel="nofollow noreferrer">https://people.cs.rutgers.edu/~allender/papers/jones.pdf</a></p>

CC BY-SA 4.0
2023-09-26T20:20:24.500Z
"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
CC BY-SA 4.0
2023-09-26T20:38:01.587Z
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
CC BY-SA 4.0
2023-09-27T07:27:55.270Z
"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
CC BY-SA 4.0
2023-09-28T14:35:23.587Z
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
CC BY-SA 4.0
2023-10-02T09:52:32.520Z
I added your comment as an edit to the answer itself, I'll accept it once the edit is accepted.
agemO
CC BY-SA 4.0
2023-10-06T19:37:32.733Z
Is there some action taht you're requesting from me?  I don't know how to "accept" an edit...
Eric Allender
CC BY-SA 4.0
2023-10-08T18:31:52.620Z
Someone accepted it, thanks for the answer!
agemO
CC BY-SA 4.0
2023-10-10T07:23:14.640Z
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
CC BY-SA 4.0
2023-10-11T09:20:40.463Z
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
CC BY-SA 4.0
2024-05-13T13:34:15.600Z
Are logspace-bounded TMs really guaranteed to be easy to invert? The only case where it seems obvious to me is when the description $d$ is also logspace-bounded.
agemO
CC BY-SA 4.0
2024-05-14T15:59:58.267Z
It is very likely that there are functions computable by logspace-bounded TMs that are hard to invert.  However, if the TM has ONE-WAY access to the input, then they are indeed, easy to invert.  Here is one reference: https://people.cs.rutgers.edu/~allender/papers/iso1l.pdf (This is a paper by me in JCSS, 1988.)
Eric Allender
CC BY-SA 4.0
2024-05-15T07:09:52.843Z
My bad, I conflated "one-way access" with "read only" instead of "one-way tape".
agemO
CC BY-SA 4.0
2023-09-26T19:52:17.497Z
2023-10-06T19:39:43.563Z
2023-10-06T19:39:43.563Z
Eric Allender
<p>For a universal Turing machine <span class="math-container">$U$</span>, the time bounded Kolmogorov complexity of a string <span class="math-container">$x$</span> is silmilar to the usual Kolmogorov complexity but limited to programs <span class="math-container">$p$</span> running in time at most <span class="math-container">$t(|x|)$</span>:
<span class="math-container">$$
K^t(x) = 
\min_{p} \{
    |p| \: : \: \mathcal{U}(p) \text{ outputs } x \text{ in less than } t(|x|) \text{ steps}
\}
$$</span></p>
<p>What are the fastest known algorithms to compute <span class="math-container">$K^t(x)$</span> (or even find the corresponding shortest programs <span class="math-container">$p$</span>)?<br />
Particularly, what about polynomial complexity <span class="math-container">$t$</span> (a.k.a. <span class="math-container">$K^{poly}$</span>) or even low degree polynomial such as <span class="math-container">$t = O(|x|)$</span> or <span class="math-container">$t = O(|x|^2)$</span>?</p>
<p>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 <span class="math-container">$p$</span> smaller than <span class="math-container">$|x|$</span> (which might never halt in the unbounded setting).</p>
<p>There are two other related time bounded Kolmogorov complexity definitions [<a href="https://www.dcs.warwick.ac.uk/%7Eigorcarb/documents/slides/rkt-icalp.pdf" rel="nofollow noreferrer">6</a>]:</p>
<p><span class="math-container">$$
K_t(x) = 
\min_{p} \{
    |p| + \log{t} \: : \: \mathcal{U}(p) \text{ outputs } x \text{ in } t \text{ steps}
\}
$$</span></p>
<p><span class="math-container">$$
KT(x) = 
\min_{p} \{
    |p| + t \: : \: \mathcal{U}(p) \text{ outputs } x \text{ in } t \text{ steps}
\}
$$</span></p>
<p>For which we have no proof yet that it is not computable in polynomial time (but we do know that the randomized version <span class="math-container">$rK_t$</span> cannot be estimated in <span class="math-container">$BPP$</span>).</p>
<p>A possible alternate definition I've never encountered is one where the time bound is a function of <span class="math-container">$|p|$</span> instead of <span class="math-container">$|x|$</span>:</p>
<p><span class="math-container">$$
K^{t^{\prime}}(x) = 
\min_{p} \{
    |p| \: : \: \mathcal{U}(p) \text{ outputs } x \text{ in less than } t^{\prime}(|p|) \text{ steps}
\}
$$</span></p>
<p>It seems to me that some long running time programs <span class="math-container">$p$</span> are allowed by the <span class="math-container">$K^t$</span> definition but forbidden by the <span class="math-container">$K^{t^{\prime}}$</span> one, so that <span class="math-container">$K^{t^{\prime}}$</span> might happen to be faster to compute.<br />
For example, <code>for i in 2^1000 print(&quot;1&quot;)</code> would be a valid candidate for a linear <span class="math-container">$t(|x|)$</span> but not for a linear <span class="math-container">$t(|p|)$</span>.</p>
<ol>
<li><a href="https://cstheory.stackexchange.com/q/8393">Efficiently computable variants of Kolmogorov complexity</a></li>
<li><a href="https://cstheory.stackexchange.com/q/7247">Kolmogorov complexity with weak description languages</a></li>
<li><a href="https://dl.acm.org/doi/pdf/10.1145/800061.808762" rel="nofollow noreferrer">Sipser, M. (1983). A complexity theoretic approach to randomness. Proceedings of the fifteenth annual ACM symposium on Theory of computing.</a></li>
<li><a href="https://arxiv.org/abs/2204.08312" rel="nofollow noreferrer">Lu, Z., Oliveira, I.C., &amp; Zimand, M. (2022). Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. ArXiv, abs/2204.08312.</a></li>
<li><a href="https://arxiv.org/abs/1301.1547" rel="nofollow noreferrer">Bauwens, B., Makhlin, A., Vereshchagin, N.K., &amp; Zimand, M. (2013). Short lists with short programs in short time. computational complexity, 27, 31-61.</a></li>
<li><a href="https://www.dcs.warwick.ac.uk/%7Eigorcarb/documents/slides/rkt-icalp.pdf" rel="nofollow noreferrer">Oliveira I.C. (2019). Randomness and intractability in Kolmogorov complexity.</a></li>
</ol>

CC BY-SA 4.0
2023-09-25T10:24:52.980Z
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
CC BY-SA 4.0
2023-09-25T11:57:46.263Z
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
<time-complexity><turing-machines><polynomial-time><kolmogorov-complexity>
Fast algorithms for time bounded Kolmogorov complexity
agemO
# Fast algorithms for time bounded Kolmogorov complexity

(Asked by: username_0 on 2023-09-23)

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](https://www.dcs.warwick.ac.uk/%7Eigorcarb/documents/slides/rkt-icalp.pdf)]:

$$
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](https://cstheory.stackexchange.com/q/8393)
2. [Kolmogorov complexity with weak description languages](https://cstheory.stackexchange.com/q/7247)
3. [Sipser, M. (1983). A complexity theoretic approach to randomness. Proceedings of the fifteenth annual ACM symposium on Theory of computing.](https://dl.acm.org/doi/pdf/10.1145/800061.808762)
4. [Lu, Z., Oliveira, I.C., & Zimand, M. (2022). Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. ArXiv, abs/2204.08312.](https://arxiv.org/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.](https://arxiv.org/abs/1301.1547)
6. [Oliveira I.C. (2019). Randomness and intractability in Kolmogorov complexity.](https://www.dcs.warwick.ac.uk/%7Eigorcarb/documents/slides/rkt-icalp.pdf)

**Tags:** time-complexity, turing-machines, polynomial-time, kolmogorov-complexity

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_2 on 2023-09-26. Score: 8 | Accepted answer

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](https://people.cs.rutgers.edu/%7Eallender/papers/jones.pdf)

> **Comments:**
> **username_0**: "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.  
> **username_0**: 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)?  
> **username_0**: "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.  
> **username_2**: In answer to the question in the 2nd comment above: Yes, it's believed that all of these measures are hard to compute.  
> **username_0**: I added your comment as an edit to the answer itself, I'll accept it once the edit is accepted.  
> **username_2**: Is there some action taht you're requesting from me?  I don't know how to "accept" an edit...  
> **username_0**: Someone accepted it, thanks for the answer!  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_0**: Are logspace-bounded TMs really guaranteed to be easy to invert? The only case where it seems obvious to me is when the description $d$ is also logspace-bounded.  
> **username_2**: It is very likely that there are functions computable by logspace-bounded TMs that are hard to invert.  However, if the TM has ONE-WAY access to the input, then they are indeed, easy to invert.  Here is one reference: https://people.cs.rutgers.edu/~allender/papers/iso1l.pdf (This is a paper by me in JCSS, 1988.)  
> **username_0**: My bad, I conflated "one-way access" with "read only" instead of "one-way tape".  

---

