Abstract:
Consider a binary string $x_0$ of Kolmogorov complexity $K(x_0)\geq n$. The question is whether there exist two strings $x_1$ and $x_2$ such that the approximate equalities $K(x_i|x_j)\approx n$ and $K(x_i|x_j,x_k)\approx n$ hold for all $0\leq i,j,k\leq2$, $i\ne j\ne k$, $i\ne k$. We prove that the answer is positive if we require the equalities to hold up to an additive term $O(\log K(x_0))$. It becomes negative in the case of better accuracy, namely, $O(\log n)$.