Skip to main content
3 of 4
edited body

Yes it is true.

Let $x$ and $y$ be strings with lengths $n$ and $C(x|y) = D =const$, $CT(x|y) \ge n$.

There is program $p$ with length $D$ such that $p(x) = y$ (we assume that we fixed some Turing machine).

Denote by $t$ - time (number of elementary operations) that need to compute $f(x)$ ($C(t|x) = O(1)$).

Let us show that $t$ is large.

Denote by $M$ all total programs with length $m$, $m \le n$.

Denote by $t_m$ maximal time of working program from $M$ with input from $\{0,1\}^n$.

Let us show that $t > t_m$ for $m = n - O(\log n)$. Before proving this statement let us explain why it proves that need. By $x$ we can get $t$. By $t$ we can get $|M|$ (or $T_m$ or $\Omega_m$) - for it need to run all programs with length $m$ on all inputs with lengths $n$ and wait time $t$.

Assume the converse. Then there is program $p_1$ with length $\le m + O(\log n)$ that write number $t_1$ that large then $t$ ($p_1$ is without input). So there is program with length $\le m + O(\log n)$ such that for any $a \in \{0,1\}^n$ it write list $(a_1,...a_k)$ such that $C(a_i|a) \le D$ and corresponding program work $\le t_1$. In list that corresponds to $x$ there is $y$. Now it is easy to see that there is total program with length $m + O(\log n)$ that correspond $x$ to $y$ (it need to fix some rule for choice some element from list). Hence $m \ge n - O(\log n)$. Hence there is $m = n - O(\log n) $ such that $t > t_m$.