# Resource-bounded variant of Kolmogorov complexity

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?

• 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.. Commented May 26, 2017 at 22:45
• @NealYoung I am asking for the shortest such TM.
– Demi
Commented May 27, 2017 at 1:24
• 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. ​ ​
– user6973
Commented May 27, 2017 at 5:42
• Not sure that'll answer your question, but have you looked at this survey of Fortnow's (Kolmogorov Complexity and Computational Complexity, 2003)? Commented May 30, 2017 at 14:02

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$$.