<p>The question was revised (in the comments) to ask: Given x, output the shortest description d such that U(d) = x in time <span class="math-container">$|d|^2$</span>.</p>
<p>Yanyi Liu and Rafael Pass showed (in FOCS 2020) that this function is hard on average if and only if one-way functions exist. (Here is a link to the paper: <a href="https://eprint.iacr.org/2020/423.pdf" rel="nofollow noreferrer">https://eprint.iacr.org/2020/423.pdf</a> ) There have been several follow-on papers.</p>
<p>The function itself is NOT known to be in FNP.</p>

CC BY-SA 4.0
2024-03-03T17:12:29.813Z
Link to the paper (on a arXiv or similar, so that the link is stable) and I’ll accept the answer.
Demi
CC BY-SA 4.0
2023-10-17T19:53:39.200Z
2024-03-04T18:16:02.123Z
2024-03-04T18:16:02.123Z
Eric Allender
<p>Consider the variant of Kolmogorov complexity, where the program is only allowed to use a bounded amount of resources.  This more closely resembles the practical situation, where decompression needs to be fast.</p>

<p>Clearly this is decidable, since determining whether a program halts while using only a bounded amount of time or space is decidable by direct simulation.  So it seems that this problem is also decidable (by exhaustive search of all possible programs).</p>

<p>If the bound is to a fixed (non-constant) polynomial, then it appears that the problem is in $\text{fNP}$.  Is it NP-hard?</p>

<p>More generally, what is the complexity of this problem?  What properties does it have?</p>

CC BY-SA 3.0
2017-05-26T22:45:18.040Z
Consider, say, the question *"Given a bit string $s$, is there a Turing machine that outputs $s$ in at most $|s|^2$ steps."*  This problem is trivially in P, because the answer is always yes.  (The TM that has $s$ encoded in its finite control.)  Perhaps the question is, *"Given a bit string $s$ and an integer $n$, is there a Turing machine of size at most $n$ that outputs $s$ in at most $|s|^2$ steps?"*...  A quick search shows [similar previous questions](https://cstheory.stackexchange.com/questions/36671/difference-between-time-bounded-and-memory-bounded-kolmogorov-complexity?rq=1)..
Neal Young
CC BY-SA 3.0
2017-05-27T01:24:43.680Z
@NealYoung I am asking for the *shortest* such TM.
Demi
CC BY-SA 3.0
2017-05-30T14:02:03.120Z
Not sure that'll answer your question, but have you looked at [this survey of Fortnow's](https://people.cs.uchicago.edu/~fortnow/papers/quaderni.pdf) (*Kolmogorov Complexity and Computational Complexity*, 2003)?
Clement C.
<cc.complexity-theory><kolmogorov-complexity>
Resource-bounded variant of Kolmogorov complexity
Demi
# Resource-bounded variant of Kolmogorov complexity

(Asked by: username_0 on 2017-05-26)

Consider the variant of Kolmogorov complexity, where the program is only allowed to use a bounded amount of resources. This more closely resembles the practical situation, where decompression needs to be fast.

Clearly this is decidable, since determining whether a program halts while using only a bounded amount of time or space is decidable by direct simulation. So it seems that this problem is also decidable (by exhaustive search of all possible programs).

If the bound is to a fixed (non-constant) polynomial, then it appears that the problem is in $\text{fNP}$. Is it NP-hard?

More generally, what is the complexity of this problem? What properties does it have?

**Tags:** cc.complexity-theory, kolmogorov-complexity
> **Comments:**
> **username_1**: Consider, say, the question *"Given a bit string $s$, is there a Turing machine that outputs $s$ in at most $|s|^2$ steps."*  This problem is trivially in P, because the answer is always yes.  (The TM that has $s$ encoded in its finite control.)  Perhaps the question is, *"Given a bit string $s$ and an integer $n$, is there a Turing machine of size at most $n$ that outputs $s$ in at most $|s|^2$ steps?"*...  A quick search shows [similar previous questions](https://cstheory.stackexchange.com/questions/36671/difference-between-time-bounded-and-memory-bounded-kolmogorov-complexity?rq=1)..  
> **username_0**: @NealYoung I am asking for the *shortest* such TM.  
> **username_2**: Not sure that'll answer your question, but have you looked at [this survey of Fortnow's](https://people.cs.uchicago.edu/~fortnow/papers/quaderni.pdf) (*Kolmogorov Complexity and Computational Complexity*, 2003)?  

---

## 1 answers

### Answer by username_3 on 2023-10-17. Score: 6

The question was revised (in the comments) to ask: Given x, output the shortest description d such that U(d) = x in time $|d|^2$.

Yanyi Liu and Rafael Pass showed (in FOCS 2020) that this function is hard on average if and only if one-way functions exist. (Here is a link to the paper: <https://eprint.iacr.org/2020/423.pdf> ) There have been several follow-on papers.

The function itself is NOT known to be in FNP.

> **Comments:**
> **username_0**: Link to the paper (on a arXiv or similar, so that the link is stable) and I’ll accept the answer.  

---

