[Recent Entries][Archive][Friends][User Info]
| November 19th, 2013 | |
|---|---|
| 10:37 pm [Link] |     Пусть X - (p,q) нестохастическая строка длины n, то есть если X \in A и K(A) < (q - \epsilon)n,то X не является типичным для A, то есть log(A) - K(X|A) > (p - \epsilon)n. Если p + q = 1, то существует (p,q) нестохастические строки. Я буду рассматривать q << 1 (то есть объект описать не очень сложно, но он ни на что не похож), хотя это абсолютно не важно. Запишем X = a_1a_2...a_n. Cтрока B - кусочек X - записывается в виде a_{i_1} ... a_{i_k}, где 0 < i_1 < ...< i_k < n + 1. Будем называть кусочек \epsilon-нормальным, если K({i_1,...,i_k}) < \epsilon * n. (например, просто подстрока X). k - размер кусочка Утверждение: если B - \epsilon-нормальный кусочек размера >qn, то K(X|B) < 3\epsilon*n. То есть весь объект можно практически восстановить по любому нормальному кусочку того же размера, что и колмогоровская сложность объекта. Поясню про "нормальность": можно извратиться и найти большой кусок человека, в котором не будет ДНК, по такому куску человека не восстановишь; нормальность требуется чтобы избежать подобных недоразумений. Current Music: Wolvserpent – A Breath In The Shade Of Time |