RUS  ENG
Полная версия
ЖУРНАЛЫ // Проблемы передачи информации // Архив

Пробл. передачи информ., 2003, том 39, выпуск 4, страницы 88–92 (Mi ppi318)

Эта публикация цитируется в 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)$.

УДК: 621.391.1:51

Поступила в редакцию: 18.02.2002
После переработки: 25.04.2003


 Англоязычная версия: Problems of Information Transmission, 2003, 39:4, 395–399

Реферативные базы данных:


© МИАН, 2024