The Kolmogorov complexity of a string $x$ is the size of the smallest Turing machine $M$ that started on empty tape produces $x$. To make it computable, we can add a bound on the time used by $M$ to produce $x$:

$C^{t}(x) = \min \{|M| : U(M) = x$ in less than $t(n)$ steps $ n = |x| \}$

And for a nice function $f(n) < n$ we can define:

$C[f(n),t(n)] = \{x : C^t(x) \leq f(n), n = |x| \}$

i.e. the set of compressible strings $x$ (whose compressed program has size less than $f(n)$) and that can be generated in time $t(n)$.

For example, for unbounded $f$, we have $C[f(n),n^k] \subseteq C[f(n),n^{k+1}] \subset C[f(n),\infty]$

  • Is the first inclusion tight?
  • What is known about the *size* of $C[f(n), n^{k+1}] \setminus C[f(n), n^{k}]$ ?
  • Are there known results for particular classes like $C[n/2,n^k]$?
  • 1
    $\begingroup$ I assume you already checked Li & Vitanyi? :-) $\endgroup$ – Juho Apr 10 '13 at 23:17
  • $\begingroup$ @Juho: to be honest I'm reading it (but very slowly ... at least until a get a hardcopy of it ;) and I'm far from fully understanding it; I found a $C[f(n),T(n)] \subset C[f(n),c2^{f(n)}T(n)]$ but a tighter version seems an open problem. I was wondering how the hell the "decompression time" (and "decompression space", but I didn't include it in my question) is distributed among the various $t(n)$s and if there are some well known results. $\endgroup$ – Vor Apr 11 '13 at 7:06

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.