# Kolmogorov Complexity vs Running Time (Edited)

Let $U$ be a universal Turing Machine. Suppose I have a Kolmogorov incompressible string $s$ of length $n$. Let $A:\{1,...,n\} \to \{0,1\}$ be an algorithm such that $A(i) = s_i$.

I believe that the time it takes for the universal Turing machine to evaluate $A$ on input $i$ should be $\Theta(n)$. I'm not familiar with Kolmogorov complexity, and I wanted to ask if the following intuition is correct

1. An upper bound on the running time of $A$ is $O(n)$, since the description of $A$ can just list the whole string $s$ and return $s_i$ on input $i$. The universal Turing machine on inputs $(A,i)$ simply reads the description of $A$ (Which is $O(n)$ in length) and outputs the $i^{th}$ coordinate (which takes time $\log n$)

2. A lower bound on the running time of $A$ can be proved as follows.

a. The description length of $A$ must be at least $n - log n - c$ for a constant $c > 0$. This is because the program $B$: "Run $A$ on every input from $1$ to $n$" has description length $DL(B) = DL(A) + log(n) + c$ and generates the string $s$. Thus $DL(B) \geq n$ and $DL(A) \geq n- \log(n) - c$.

b. The universal Turing machine $U$ on input $(A,i)$ needs to read both $A$ and $i$, which requires at least $DL(A) + \log n \geq n-c$ operations.

Is this intuition correct? Or am I missing something big about Kolmogorov complexity?

• Looks fine to me at first glance, but the odd thing is that this is "non-uniform": For each $n$ and each incompressible string $s$, there's a different TM $A$. – usul Jan 21 '15 at 20:00

## 1 Answer

It really depends on your computation model. Suppose for example a model which allows random "seek" instructions, say the RAM machine. The algorithm $A$ can just include a description of the string, and on input $i$ you output the $i$th bit of the string. Conceivably, a universal Turing machine (running on a RAM machine) can execute this algorithm in time $O(\log n)$, especially if we engineer it to specifically handle algorithms of this type.

Any proof that a universal Turing machine (running on an actual Turing machine) requires time $\Theta(n)$ thus needs to appeal specifically to the Turing machine model. In particular, you claim that the universal Turing machine $U$ must read all of $A$ and $i$. But in fact, for any given string $s$ we can construct a universal Turing machine whose programs come in two types: (1) output $s$; (2) everything else. Such a Turing machine can "simulate" $A$ in time $O(\log n)$. The correct claim you should try to prove thus needs to accommodate finitely many exceptions, unless you are fixing a universal Turing machine. (On second thought, it's not clear whether you can pull it off while keeping the string random. Indeed, it seems you won't be able to recognize the program $A$ without reading all of it, which would take time $n$ if the string is Kolmogorov random.)

Even if we fix a universal Turing machine, it's not clear that $A$ necessarily takes time $O(n)$. We can arrange for $A$ to first output $n!$ many zeroes, then erase them and proceed as in your algorithm. Perhaps you meant $A$ to be the one with the lowest time complexity? (say the one minimizing the maximal execution time over all indices)

• Thanks for the answer. As for the Turing Machine definitions, I think that's mostly where I don't trust my intuition. I'm used to programs being constant size and inputs growing asymptotically. Thus, when accounting for the running time of some Turing machine $M$ on input $x$, I never cared about the time it takes to read the program $M$". Am I deviating in some way from the standard model by having $M$ be really large (needing $O(n)$ bits to describe), and accounting for the fact that the universal machine has to read $M$ when analyzing the running time of the algorithm? – Asterix Jan 22 '15 at 19:07
• Not at all, a universal machine is just like any other machine, and it also has to read its input. What I'm pointing out is that you can hard-code a specific string into the universal machine in order to make it easy for the machine to generate it. It's not clear whether you can do it while keeping this string Kolmogorov random, however. – Yuval Filmus Jan 22 '15 at 21:17