|
Проблемы передачи информации, 2003, том 39, выпуск 4, страницы 88–92
(Mi ppi318)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Большие системы
Системы строк с большой взаимной сложностью
М. В. Вьюгин Московский государственный университет им. М. В. Ломоносова
Аннотация:
Рассмотрим двоичное слово $x_0$ колмогоровской сложности $K(x_0)\geq n$. Вопрос
состоит в следующем: найдутся ли два других слова $x_1$ и $x_2$ таких, что выполнены
следующие приблизительные равенства $K(x_i|x_j)\approx n$ и $K(x_i|x_j,x_k)\approx n$
для всех $0\leq i,j,k\leq2$, $i\ne j\ne k$, $i\ne k$? Доказано, что ответ положителен,
если требовать выполнения равенств с точностью до аддитивного члена вида
$O(\log K(x_0))$, и отрицателен с большей точностью, а именно с точностью
до $O(\log n)$.
Поступила в редакцию: 18.02.2002 После переработки: 25.04.2003
Образец цитирования:
М. В. Вьюгин, “Системы строк с большой взаимной сложностью”, Пробл. передачи информ., 39:4 (2003), 88–92; Problems Inform. Transmission, 39:4 (2003), 395–399
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ppi318 https://www.mathnet.ru/rus/ppi/v39/i4/p88
|
Статистика просмотров: |
Страница аннотации: | 374 | PDF полного текста: | 85 | Список литературы: | 39 | Первая страница: | 1 |
|