Systems of Strings with High Mutual Complexity |
| |
Authors: | Vyugin M V |
| |
Affiliation: | (1) Royal Holloway University of London. M.V. Lomonosov Moscow State University, Russia |
| |
Abstract: | Consider a binary string x
0 of Kolmogorov complexity K(x
0) n. The question is whether there exist two strings x
1 and x
2 such that the approximate equalities K(x
i
x
j
) n and K(x
i
x
j
, x
k
) n hold for all 0 i, j, k 2, i j k, i 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). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|