RUS  ENG
Full version
JOURNALS // Problemy Peredachi Informatsii // Archive

Probl. Peredachi Inf., 2003 Volume 39, Issue 4, Pages 88–92 (Mi ppi318)

This article is cited in 3 papers

Large Systems

Systems of Strings with Large Mutual Complexity

M. V. V'yugin

M. V. Lomonosov Moscow State University

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)$.

UDC: 621.391.1:51

Received: 18.02.2002
Revised: 25.04.2003


 English version:
Problems of Information Transmission, 2003, 39:4, 395–399

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025