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?

  • $\begingroup$ 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.. $\endgroup$
    – Neal Young
    Commented May 26, 2017 at 22:45
  • 2
    $\begingroup$ @NealYoung I am asking for the shortest such TM. $\endgroup$
    – Demi
    Commented May 27, 2017 at 1:24
  • $\begingroup$ The problem is in NPO, but I don't see why there should be polynomial-length proofs of lower bounds, so I don't see why the problem should be in FNP. ​ ​ $\endgroup$
    – user6973
    Commented May 27, 2017 at 5:42
  • $\begingroup$ Not sure that'll answer your question, but have you looked at this survey of Fortnow's (Kolmogorov Complexity and Computational Complexity, 2003)? $\endgroup$
    – Clement C.
    Commented May 30, 2017 at 14:02

1 Answer 1


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.

  • $\begingroup$ Link to the paper (on a arXiv or similar, so that the link is stable) and I’ll accept the answer. $\endgroup$
    – Demi
    Commented Mar 3 at 17:12

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.