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
    May 26 '17 at 22:45
  • 1
    $\begingroup$ @NealYoung I am asking for the shortest such TM. $\endgroup$
    – Demi
    May 27 '17 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
    May 27 '17 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.
    May 30 '17 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.