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)$.
Citation:
M. V. V'yugin, “Systems of Strings with Large Mutual Complexity”, Probl. Peredachi Inf., 39:4 (2003), 88–92; Problems Inform. Transmission, 39:4 (2003), 395–399