|
Problemy Peredachi Informatsii, 2003, Volume 39, Issue 4, Pages 88–92
(Mi ppi318)
|
|
|
|
This article is cited in 3 scientific papers (total 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)$.
Received: 18.02.2002 Revised: 25.04.2003
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
Linking options:
https://www.mathnet.ru/eng/ppi318 https://www.mathnet.ru/eng/ppi/v39/i4/p88
|
Statistics & downloads: |
Abstract page: | 376 | Full-text PDF : | 88 | References: | 41 | First page: | 1 |
|