By $C(|)$ denote conditional complexity.

By $CT(|)$ denote total conditional complexity.

For every n there exist two strings $x$ and $y$ of length $n$ such that $C(x|y) = O(1)$ but $CT(x|y) \ge n $.

It is proved there: http://arxiv.org/pdf/1204.0198.pdf pages 5-6.

It is easy to see that $x$ have the same information as $y$ (Let us denote it $ x \sim y$)

What is the information?

By $T_n$ denote number of total programs with length $< n$.( $T_n \sim N_k$ - number of integers with complexity $\le n$. $N_k \sim \Omega_n$ - the first $n$ bits Chaitin's number.)

Let $x=x_n$ and $y=y_n$ where $x_n$ and $y_n$ are the same as in article. Then $x \sim T_n$: we can play this computable game until Alice add $x_n$ - so we find $T_n$.

Question: let $x$ and $y$ have lengths $n$ , $C(x|y) = O(1)$ and $CT(x|y) \ge n $.

Is it true that $x \sim T_n$ necessarily?


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


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.