\documentclass[12pt]{article}
\usepackage{amsthm,amsmath,amssymb,amsfonts,latexsym}
%\usepackage[indentheadings]{russcorr}
\usepackage[koi8-r]{inputenc}
\usepackage[russian]{babel}

\usepackage{fullpage}

%\tolerance 600

\newtheorem{theorem}{Теорема}
\newtheorem{lemma}[theorem]{Лемма}
\newtheorem{corollary}[theorem]{Следствие}
\newtheorem{definition}[theorem]{Определение}

\title{Информационное расстояние для сложных строк}
\author{М. В. Вьюгин, Ан. А. Мучник}

\date{}

\newcommand{\pair}[1]{\langle #1\rangle}
\newcommand{\Z}{{\bf Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\dist}{d}
\newcommand{\mc}{M}
\newcommand{\mm}{C}
\newcommand{\nc}{N}
\newcommand{\nd}{D}
\newcommand{\ks}{K}
\newcommand{\ncs}{\tilde N}
\newcommand\es{\Lambda}
\renewcommand{\le}{\leqslant}
\renewcommand{\ge}{\geqslant}

\begin{document}

\maketitle

\begin{abstract}
        %
Мы доказываем, что для произвольного слова $x_0$, имеющего
колмогоровскую сложность $n$ или больше, найдется набор слов
$x_1, x_2, \ldots, x_m$, для которых с высокой точностью
выполнены приблизительные равенства $K(x_i|x_j)\approx n$ для
всех $0\le i,j\le m$, $i\neq j$. Рассмотрены возможные усиления
и обобщения этого результата.
        %
\end{abstract}

\section{Введение}

\emph{Условная колмогоровская сложность конечного слова $x$ при
условии $y$} определяется как длина кратчайшей программы $p$,
преобразующей $y$ в~$x$ (строгое определение см. ниже). Она
обозначается $K(y|x)$. \emph{Безусловная колмогоровская
сложность} $K(x)$ слова $x$ равна $K(x|\Lambda)$, где $\Lambda$
--- пустое слово.


Пусть дано некоторое слово $x_0$. Мы хотим выбрать слова $x_1,
x_2, \dots , x_m$ так, чтобы набор слов $\{ x_0, x_1, \dots ,
x_m \}$ удовлетворял заданным ограничениям на условные
сложности. В общем виде ответ на вопрос, при каких ограничениях
это возможно, неизвестен (даже для пустого $x_0$). Некоторые
частные случаи рассмотрены в настоящей работе.

В работе~\cite{mvyugin} было доказано, что для всякого числа $n$
и слова $x$ такого, что $K(x)\ge 2n$, существует слово $y$, для
которого
        $$
K(x|y)\approx n, K(y|x)\approx n
        $$
с точностью до слагаемого $O(1)$.

В настоящей работе мы обобщаем этот резульатат.
Теорема~\ref{theorem1-2} утверждает, что для каждого
положительного целого числа $m$ и для любого слова $x_0$
сложности $K(x_0)\ge 2m^2 (n+1)$ найдутся такие слова $x_1, x_2,
\dots , x_m$, что
       $$
K(x_i|x_j)=n+O(\log m),\ 0\le i,j \le m,\ i\neq j.
       $$
При более слабом условии $K(x_0)>n$ мы можем получить несколько
худшую оценку с дополнительным членом $O(\log n)$ в правой
части. В разделе~\ref{sectsmall} мы доказываем, что погрешность
порядка $O(\log m)$ неизбежна.

Мы рассматриваем возможность дальнейшего обобщения этого
результата. Можно ли, скажем, наложить ограничение также на
условные сложности с двумя условиями вида $K(x_i|x_j,x_k)$?
Легко видеть, что с логарифмической точностью результат
останётся верен, но с точностью $O(1)$ это уже не так
(Теорема~\ref{impos-th}). Этот результат был получен в
работе~\cite{vyugin-ppi}. Мы приводим другое его доказательство.

Рассматривая возможность обобщения основного результата, по ходу
дела мы доказываем следующее утверждение о существовании
``неделимого'' слова, представляющее самостоятельный интерес.
Зафиксируем числа $\alpha$ и $\beta$, для которых $\alpha>0$,
$\beta>0$ и $\alpha + \beta = 1$. Можно ли произвольное слово
$x$ разделить в пропорции $\alpha : \beta$? Формально это
означает: верно ли, что для любого слова $x$ найдется такое
слово $y$, что
        %
\begin{eqnarray*}
        %
K(y|x) &\approx & 0, \\
K(y) &\approx & \alpha K(x), \\
K(x|y) &\approx & \beta K(x).
        %
\end{eqnarray*}
        %
Этот вопрос, как и предыдущие, имеет разные варианты в
зависимости от желаемой степени точности. Легко видеть, что если
потребовать выполнения приблизительных равенств с точностью до
$O(\log K(x,y))$, ответ положителен. Достаточно перейти от слова
$x$ к кратчайшей программе, вычисляющей $x$ и взять в качестве
$y$ начальный кусок этой программы длины $\alpha K(x)$. Можно
было бы предположить, что результат остается верным и при
точности $O(1)$, однако это не так. Теорема~\ref{undiv-th} даёт
отрицательный ответ при точности $\frac{1}{2}\log \log K(x)$:
существует слово $x$, которое нельзя разделить ни в какой
пропорции (любое слово $y$, простое относительно $x$ либо имеет
малую безусловную сложность, либо мало отличается от $x$).
Теорема также дает нижнюю оценку на сложность такого~$x$.

Использованный при доказательстве Теоремы~\ref{undiv-th} метод
``просеивания'' применяется и при доказательстве
теорем~\ref{theorem3} и~\ref{impos-th}.

\section{Колмогоровская сложность}\label{kolmcompl}

Назовем \emph{языком программирования} произвольную (частичную)
вычислимую функцию $F$ из $\{ 0,1 \}^{*}\times \{ 0,1 \}^{*}$ в
$\{ 0,1 \}^{*}$. Первый аргумент $F$ назовём \emph{программой},
второй~--- \emph{входом}, а значение $F(p,x)$~---
\emph{результатом} работы программы $p$ на входе $x$. Язык
программирования $U$ называется \emph{универсальным}, если для
любого другого языка программирования $F$ найдется такая
константа $t_F$, что $U(t_F p, x)=F(p,x)$ для любых $p,x$.
Зафиксируем произвольный универсальный язык программирования $U$
и определим условную колмогоровскую сложность $K(x|y)$ как длину
кратчайшей программы $p$, для которой $U(p,y)=x$. Безусловную
сложность $K(x)$ определим как $K(x|\Lambda)$.

Мы будем использовать следующие хорошо известные факты: для
каждого алгоритма $A$ найдется такая константа $c$, что
$K(A(x))\le K(x)+c$ для всех $x$, на которых $A$ заканчивает
работу. Для каждого $n$ существует не более $2^n$ строк $x$ с
$K(x)<n$. Мы также будем использовать равенство
$|K(x,y)-K(x)-K(y|x)|=O(\log K(x,y))$, доказанное Колмогоровым и
Левиным (см. \cite{li-vitanyi}).

Мы будем оценивать сложность сверху с помощью такого простого
замечания. Пусть есть перечислимое семейство $A_n$ множеств
слов. (Перечислимость множества $A_n$ означает перечислимость
множества $\{\langle n,x\rangle\mid x \in A_n\}$.) Пусть
$|A_n|<2^n$ для всех $n$. Тогда найдется такая константа $c$,
что $K(x)<n+c$ для всех $n$ и всех $x \in A_n$.

\section{Положительный результат}\label{sectionmain}

Начнём с такого простого замечания: \emph{для любого слова
$x_0$, сложность которого больше $n$, и для любого $m$ можно
построить слова $x_1,\ldots,x_m$ с таким свойством}:
        $$
K(x_i|x_j)=n+O(\log K(x_0))+O(\log m)
        $$
\emph{при всех $i,j\in\{0,1,\ldots,m\}$} (\emph{при $i\ne j$}).

В самом деле, слово $x_0$ можно заменить на его кратчайшее опи-
сание: условная сложность перехода в обе стороны не больше
$O(\log K(x_0))$. Затем слова $x_1,\ldots x_m$ строим так:
отбрасываем от (уже несжимаемого) $x_0$ последние $n$ битов и
заменяем их на случайные $n$ битов (свои для каждого
$i=1,\ldots,m$). Точнее, мы берём слово длины $mn$, разрезаем
его на $m$ кусков по $n$ битов, и заменяем последние $n$ битов в
$x_0$ на эти куски.

Мы не приводим подробности этой конструкции, поскольку нас
интересует более точный результат, с погрешностью $O(1)+O(\log
m)$. В нём, однако, нам придётся усилить предположение (нижнюю
оценкку на сложность $x_0$):

\begin{theorem}\label{theorem1-2}
        %
Для любых натуральных чисел $m$ и $n$ и любого двоичного слова
$x_0$ с
        $$
K(x_0)>n(m^2+m+1)+3\log m +O(1)
        $$
существуют слова $x_1, \dots, x_m$, для которых
        $$
n\le K(x_i|x_j)\le n+3\log m +O(1)
        $$
при $0 \le i,j \le m$, $i\neq j$.
        %
\end{theorem}

\noindent {\bf Доказательство} использует игровой подход:
утверждение теоремы выводится из существования выигрышной
стратегии в некоторой игре. Каждой паре значений $n$ и $m$
соответствует своя игра. Она происходит на $m$-дольном графе с
бесконечными долями. Мы считаем, что вершинами каждой доли $X_i$
($i=0,\ldots,m$) являются все двоичные слова.

Два игрока, Математик (М) и Природа (П), проводят рёбра,
соединяющие вершины из разных долей графа (М проводит
ненаправленные рёбра, а П~--- направленные). Игроки ходят по
очереди; ход состоит в добавлении конечного числа рёбер.
Математик может также ``отметить'' (объявить ``простой'') любую
вершину в доле $X_0$ или несколько таких вершин Каждый игрок
может пропустить свой ход (не отметить ни одного ребра). Игроки
должны соблюдать следующие ограничения:
        %
\begin{itemize}

\item М имеет право отметить не более $N=m2^{n+1+nm(m+1)}$
вершин (в доле $X_0$).

\item Для каждой вершины $x_i\in X_i$ и для каждого $j\neq i$ М
имеет право провести не более $m(m+1)2^n$ рёбер, соединяющих
$x_i$ с вершинами из $X_j$.

\item Для каждой вершины $x_i\in X_i$ и для каждого $j\neq i$ П
имеет право провести не более $2^n$ рёбер, ведущих из $x_i$ в
вершины доли~$X_j$.

\end{itemize}

Игра бесконечна (партия представляет собой бесконечную
последовательность чередующихся ходов М и П).

\textbf{Условие выигрыша.} М выигрывает в данной (бесконечной)
партии, если для любой не отмеченной вершины $x_0\in X_0$
существуют такие вершины $x_1, \dots, x_m$ из соответствующих
долей графа, что любые две вершины из числа ${x_0, \dots, x_m}$
на некотором шаге соединены М-ребром и ни на каком шаге не
соединены П-ребром.

Заметим, что М может провести из $x_0$ ограниченное число рёбер.
Поэтому выигрыш М означает, что любая вершина $x_0\in X_0$ либо в
некоторый момент будет отмечена, либо в некоторый момент будет
соединена М-рёбрами с вершинами $x_1,\ldots,x_m$, которые
соединены М-рёбрами между собой, и никакие из этих М-рёбер не
будут впоследствии продублированы П-рёбрами (ни в ту, ни в
другую сторону~--- напомним, что П-рёбра ориентированы, а
М-рёбра~--- нет).

Теперь доказательство теоремы разбивается на две части. В
лемме~\ref{lemma1} мы докажем существование выигрывающей
стратегии для М, вычислимой равномерно по $n$ и $m$. Отдельно мы
покажем, что из существования такой стратегии следует
утверждение теоремы.

Начнём с последнего. Пусть П придеживается такой стратегии: как
только обнаруживается пара $\langle x,y\rangle$, для которой
$K(x|y)<n$, П проводит ребра из $y$ в $x$ для всех пар долей.
(Множество пар с условной сложностью меньше~$n$ перечислимо, так
что эта стратегия вычислима.)

Лемма гарантирует, что М выигрывает против этой стратегии. Это
означает, что для каждой не отмеченной им вершины $x_0\in X_0$
после достаточного числа ходов найдётся набор вершин $x_1\in
X_1, \dots, x_m\in X_m$ с таким свойством: каждая пара вершин
$\langle x_i, x_j\rangle$ в наборе $\langle x_0,\ldots,x_m$
соединена М и не соединена (и не будет соединена) П.

Сначала убедимся, что вершины $x_0$, которые были объявлены М
``простыми'', действительно имеют малую сложность. В самом деле,
для восстановления отмеченной вершины $x_0$ достаточно знать
$m$, $n$ и порядковый номер $x_0$ среди всех элементов,
отмеченных в этой игре. Мы можем дополнить двоичную запись
последнего числа нулями слева так, чтобы длина записи оказалась
равна $\log N$. Тогда по этой записи мы сможем восстановить $n$
(зная $m$). Таким образом, мы можем задать $x_0$ словом длины
$\log N +2\log m + O(1)$, что противоречит условию теоремы.

Другими словами, слово $x_0$, для которого $K(x_0)>\log N+2\log
m+O(1)$, не может быть отмечено в $(m,n)$-игре. Возьмем любую
такую вершину $x_0$. Поскольку М выигрывает, этой вершине
соответствуют некоторые слова $x_1, \dots, x_m$. Так как
$x_0,\ldots,x_m$ не соединены Природой, то $K(x_i|x_j)\ge n$.
Остается убедиться в том, что $K(x_i|x_j)$ ненамного больше $n$.

Мы сделаем это тем же способом, который был использован для
задания отмеченных вершин. Зададим вершину $x_i\in X_i$ при
известной вершине $x_j\in X_j$, указав порядковый номер (в
порядке появления в игре) М-ребра, соединяющего эти вершины,
среди всех М-рёбер, соединяющих $x_j$ с вершинами из доли $X_i$.
Затем дополним двоичную запись этого числа нулями слева так,
чтобы длина этой записи оказалась равна $n+2\log m+1$. Имея эту
двоичную запись, а также $m$ и $x_j$, можно найти $n$ и затем
$x_i$. Поэтому сложность $K(x_i|x_j)\le n+3\log m+O(1)$

Осталось доказать упомянутую лемму:

\begin{lemma}\label{lemma1}
        %
В описанной игре существует выигрывающая стратегия для М. Эта
стратегия вычислима равномерно по $m$, $n$.
        %
\end{lemma}

\noindent {\bf Доказательство.}

Опишем общую схему этой стратегии. В каждый момент игры М для
каждой ещё не отмеченной им вершины $x_0\in X_0$ указывает
некоторую клику: $m+1$ вершин (по одной в каждой доле графа,
включая вершину $x_0$ в доле $X_0$), соединённых М-рёбрами
(попарно). Эти клики не пересекаются для разных $x_0$.
Изначально каждое слово $x\in X_0$ соединено с такими же словами
во всех $X_i$. (Строго говоря, для этого нужно на первом же ходу
провести бесконечно много рёбер, но их можно произвольно
растянуть во времени, так как ходы противников независимы, а
условие выигрыша проверяется ``после окончания'' бесконечной
партии.)

Рёбра, входящие в эти клики, будем называть \emph{активными}
М-рёбрами. Стратегия М ожидает, пока одно из этих рёбер будет
``закорочено'' П-ребром (с теми же концами) в одну из двух
сторон. По тем же соображениям о возможности ``откладывания'' мы
можем без ограничения общности предполагать, что П делает лишь
ходы, закорачивающие одно из активных рёбер (другие ходы П
откладываются до момента, когда они станут существенными, то
есть будут портить активные рёбра; если этого не произойдёт, то
эти ходы не помешают выигрышу в пределе). Когда клика испорчена,
М её ``распускает'' и либо объявляет входящую в неё вершину
$x_0$ простой, либо строит новую клику для $x_0$.

Опишем стратегию М. Для каждой вершины (в любой доле) М хранит
набор чисел~$I$, называемый \emph{индексом} этой вершины. Набор
этот состоит из $(m+1)m$ чисел и нумеруется упорядоченными
парами $(i,j)$, где $i$ и $j$ принимают значения от $0$ до $m$ и
$i\ne j$; соответствующая компонента индекса обозначается
$I_{i,j}$. Изначально индексы всех вершин нулевые (все
компоненты индекса любой вершины равны нулю).

Индекс меняется следующим образом. Пусть П испортил клику
$x_0,x_1,\ldots,x_m$ (вершина $x_i$ в доле $X_i$), проведя
П-ребро из $x_i$ в $x_j$. Тогда во всех вершинах, входящих в
клику, $(i,j)$-ая компонента индекса увеличивается на единицу.

Стратегия М состоит в том, что испорченная клика аннулируется, и
либо создаётся новая клика для того же $x_0$, состоящая из
вершин равного с $x_0$ индекса, либо $x_0$ объявляется простой.
Второе происходит, если первое не удаётся (то есть не удаётся
найти в каждой доле не входящую в клики вершину, имеющую тот же
индекс, что $x_0$, причём так, что никакие из двух вершин этой
новообразуемой клики не соединены П-ребром).

При этом, как легко видеть, поддерживаются следующие свойства:

\begin{itemize}

\item у любой клики индексы всех её вершин равны;

\item если клика содержит вершины $x_i$ и $x_j$ в долях $X_i$ и
$X_j$, а $I$~--- индекс вершин этой клики, то $I_{i,j}$ равно
числу проведённых к этому моменту П-рёбер из вершины $x_i$ в
долю $X_J$ и одновременно равно числу проведённых к этому
моменту П-рёбер из доли $X_i$ в вершину $x_j$.

\item в каждый момент лишь конечное число вершин имеют ненулевые
индексы, и количества вершин данного индекса во всех долях
равны;

\item количества ``свободных'' (не входящих в клики) вершин во
всех долях конечны и равны; в $X_0$ это в точности неотмеченные
вершины (из сказанного следует также, что количества
\textsl{свободных} вершин данного индекса во всех долях равны);

\item индекс данной вершины со временем может только расти
(покомпонентно); на каждом шаге может возрасти индекс только у
одной из вершин в каждой доле (одна из компонент увеличивается
на единицу).

\end{itemize}

Проверим, что эти свойства действительно сохраняются.
Прежде всего заметим, что после появления П-ребра и коррекции
индекса соотношения между значениями компонент индекса и
количествами П-рёбер сохраняются (добавилось ребро из $x_i$ в
$x_j$, и в обеих вершинах $x_i$ и $x_j$ индекс изменился
правильно). При образовании новой клики мы соединяем вершины
одинакового индекса, и условия (которые формулируются локально
для каждой из вершин) не нарушаются.

Теперь оценим число М-рёбер, выходящих из данной вершины в
данную долю. Новое такое ребро (и ещё $m-1$ рёбер в другие
доли~--- некоторые из них, впрочем, могут уже существовать)
появляется, когда вершину включают в новую клику; эта клика либо
так и останется (и тогда новых М-рёбер, соседних с нашей
вершиной, не появится), либо будет потом распущена. При каждом
роспуске одна из компонент индекса увеличивается на единицу, и
поэтому общее число таких случаев не превосходит максимально
возможной суммы всех $m(m+1)$ компонент индекса. А из условий
вытекает, что $I_{i,j}$ не превышает числа П-рёбер, ведущих из
вершины $x_i$ в долю $X_j$, то есть $2^n$. (Заметим, что
априорных ограничений на число рёбер, ведущих из $X_i$ в $x_j$,
нет, но поскольку два числа равны, достаточно ограничить одно из
них.) Поэтому общее число М-рёбер из данной вершины в данную
долю не превосходит $m(m+1)2^n$, как и требуется.

Условия про равенства количества вершин данного индекса
(свободных и вообще) также очевидны: свободные вершины
появляются, когда мы распускаем клику, и пропадают, когда мы
собираем новую клику; в обоих случаях все вершины имеют равный
индекс.

Осталось оценить сверху число отмеченных вершин (=свободных в
доле $X_0$). Мы сделаем это для каждого индекса, а потом умножим
на число возможных индексов, которое не превосходит
$2^{nm(m+1)}$, поскольку каждая из $m(m+1)$ компонент индекса
имеет $2^n$ возможных значений. Докажем, что для данного индекса
число отмеченных вершин этого индекса не превосходит $m2^{n+1}$,
то есть что новые вершины не будут отмечены, когда уже есть
столько отмеченных вершин этого индекса (и столько же свободных
вершин этого индекса в каждой доле). В самом деле, покажем, что
в этом случае удастся найти новую клику такого индекса. Что для
этого нужно? рассматривая долю за долей, будем выбирать среди
вершин данного индекса одну, которая ещё не соединена П-рёбрами
с ранее выбранными. Поскольку все компоненты индекса ограничены
числом $2^n$ (см. выше), то с каждой из уже выбранных вершин
соединено не более $2^{n+1}$ штук (умножаем на два, потому что в
две стороны), а уже просмотренных долей максимум~$m$. Таким
образом, число отмеченных вершин не превосходит
$m2^{n+1}2^{nm(m+1)}$.

Лемма (и тем самым теорема) доказана.~$\Box$

Отметим следующее простое следствие теоремы~\ref{theorem1-2}. В
этой теореме мы доказали, что при достаточно большом $K(x_0)$
можно найти слова $x_1,\ldots,x_m$ с нужными условными
сложностями с точностью до $O(\log m)$. С другой стороны,
замечание в начале раздела показывает, что можно найти слова с
нужными условными сложностями с точностью до $O(\log
K(x_0))+O(\log m)$. Комбинируя эти утверждения, получает
следующее:


\begin{theorem}\label{corollary1}
        %
Для каждого числа $m$ найдется константа $c$ такая, что для
всякого $n$ и всякого двоичного слова $x_0$ такого, что
$K(x_0)>n$ выполнено следующее: существует набор слов $x_1,
\dots, x_m$ удовлетворяющий условию $|K(x_i|x_j)-n|=O(\log n)+c$.
если $0 \le i,j \le m$ и $i\neq j$.
        %
\end{theorem}

В этой теореме константа, скрытая в $O(\log n)$, не зависит от
$m$, а $c$ может зависеть от $m$. В разделе~\ref{sectsmall} мы
увидим, что $c$ есть $\Theta(\log m)$.

Теперь мы можем сделать попытку обобщить положительный результат
Теоремы~\ref{theorem1-2} для случая $m=1$ в следующем направлении.

Зафиксируем целые числа $l$ и $k$.
Пусть $x$ -- любое слово удовлетворяющее условию $K(x)\ge l$.
Мы хотим найти слово~$y$ такое, что
        $$
 K(x|y)\approx l, \qquad K(y|x)\approx k.
        $$
Нам известно следующее:

(1)~Если $l\le k$, можно найти~$y$ такое, что $K(x|y)=l+O(\log l)$, $K(y|x)=k+O(\log l)$. Это простой вывод из
Теоремы~\ref{corollary1} в случае $m=1$: выберем $y$ таким, что $K(x|y)\approx K(y|x)\approx l$ (с точностью до
аддитивного члена вида $O(\log l)$) и добавим к нему $k-l$ случайных битов.

(2)~Этот результат перестает быть верным в случае $k<l-\log l -c$.
Действительно, пусть $x$ -- неделимое слово из утверждения
Теоремы~\ref{undiv-th}. Для такого $x$ не существует $y$
удовлетворяющего условиям $K(y|x)\approx k$ и $K(x|y)\approx l$,
т.к. $K(x)\ge 3k$ по условию Теоремы~\ref{undiv-th}.













\section{Неделимые слова}\label{chap-undivis}


Следующая Теорема~\ref{undiv-th} дает пример ``неделимого''
слова. Такое слово $x$ обладает тем свойством, что любое слово,
простое относительно $x$, либо просто само по себе, либо
приблизительно эквивалентно $x$. Откуда следует, что мы не можем без
дополнительной информации разделить слово $x$ на две
нетривиальные (ненулевые) части.

Конструкция, испольуемая для доказательства этого результата пригодится нам при доказательстве Теорем~\ref{theorem3} и~\ref{impos-th}.

\begin{theorem}\label{undiv-th}
Существует константа $c>0$ такая, что для любого натурального числа $k$ существует слово $x$ такое, что $K(x)\ge 3k$ и
удовлетворяющее условию: для любого слова $y$, если $K(y|x)<k$, то либо
$$
K(y)<k+c,
$$
либо
$$
K(x|y)<k+c.
$$
\end{theorem}
\noindent {\bf Доказательство.} Для доказательства этой теоремы мы используем игровой подход. Определим игру, зависящую
от параметра $k$. Пусть $M=3k 2^{2^k}$, $N=2^M$, $X=\{  0,1 \}^M$ и $Y=\{  0,1 \}^*$.

Есть два игрока, Математик и Природа. Игра -- это процесс построения двудольного графа. $X$ будет первой долей этого
графа, а $Y$ -- второй. Игроки по очереди делают ходы. Природа на своем ходу может создать одно или несколько
направленных ребер, выходящих из вершин $x\in X$ в вершины из $Y$. М на своем ходу может отметить любую вершину
$y\in Y$, а также создать одно или несколько направленных ребер, идущих из некоторых вершин $y\in Y$ в вершины из $X$.
Каждый игрок может пропустить свой ход.

Игра продолжается бесконечное число ходов.

Имеется два ограничения:
\begin{itemize}
\item{(1)} Исходящие степени вершин М и П не
могут превзойти $2^k$.
\item{(2)} Число вершин из $Y$, отмеченных Математиком не превышает
$2^k$.
\end{itemize}

Цель Математика состоит в том, чтобы после бесконечного числа шагов нашлось как минимум $2^{3k}$
вершин $x\in X$ таких, что для любой вершины $y\in Y$, соединенной с $x$ ребром Природы выполнено следующее: либо $y$
отмечена Математиком, либо она соединена с $x$ ребром Математика.

По Лемме~\ref{lemma-undiv}, существует выигрывающая стратегия для Математика. Остается вывести утверждение теоремы из
этого факта.

Пусть Природа следует следующей стратегии. Она перечисляет все пары $(x,y)$ такие, что $K(y|x)<k$ и, для каждой такой
пары проводит ребро, идущее из $x\in X$ в $y\in Y$. Так как Математик имеет выигрывающую стратегию, имеется $x_0\in X$
такое, что всякое $y\in Y$ соединенное с $x$ ребром Природы, либо отмечено, либо соединено с $x$ ребром Математика.

Мы можем сделать игру независимой от параметра $k$. Рассмотрим различные игры для разных значений $k$.


Пусть $y\in Y$ отмечено Математиком в $k$-й игре. Тогда для задания $y$ достаточно $k$-битного слова. Таким словом
может быть двоичная запись номера $y$ среди всех вершин, отмеченных в $k$-й игре (напомним, что число таких вершин не
превосходит $2^k$), дополненная слева нулями до длины $k$. Параметр $k$ также может быть восстановлен по этому слову.
Таким образом $K(y)<k+c_1$ для некоторой константы $c_1$, зависящей лишь от выбора универсального языка
программирования.

Пусть теперь есть ребро Математика, идущее из $y$ в $x$. Рассуждение, аналогичное уже неоднократно применявшимся может
быть использовано для того, чтобы убедиться в том, что $K(x|y)<k+c_2$, где $c_2$ -- константа, зависящая только от
выбора универсального языка программирования.

По Лемме~\ref{lemma-undiv}, Математик имеет выигрывающую стратегию, которая выигрывает против вышеописанной стратегии
Природы. Это означает, что найдется как минимум $2^{3k}$ слов $x$ длины $M$ таких, что каждое слово $y$ со свойством
$K(y|x)<k$, либо отмечено, либо соединено с $x$ ребром Математика. Т.е. $y$ таково, что либо $K(y)<k+c_1$, либо
$K(x|y)<k+c_2$. Очевидно, среди этих $2^{3k}$ слов найдется слово $x_0$ сложности $K(x_0)\ge 3k$.

Для получения первого утверждения теоремы остается определить $c=\max\{ c_1,c_2 \}$.

\begin{lemma}\label{lemma-undiv}
В игре из доказательства Теоремы~\ref{undiv-th}, Математик имеет выигрывающую стратегию. Эта стратегия вычислима
равномерно по $k$.
\end{lemma}
\noindent {\bf Доказательство.} Здесь мы используем метод ``просеивания'', другие применения которого можно
найти, например, в~\cite{vervyu}.

Разобьем стратегию М на несколько этапов. Число этапов не превосходит $2^k$. Пусть $N_0=|X|$ и
$X_0=X$.

Опишем первый этап. М ждет до тех пор, пока П не создаст ребра, выходящие из $x\in X_0$ для каждого $x\in
X_0$. Если этого не происходит, М выигрывает т.к. $x\in X_0$ без исходящих ребер удовлетворяет условию
выигрыша.

Без потери общности предположим, что из каждой вершины $x\in X_0$ исходит в точности одно ребро П.
Остальные ребра мы просто не будем рассматривать на этом этапе.

Если каждая вершина $x\in X_0$ имеет одно исходящее ребро, есть две возможности:
\begin{itemize}
\item{} Существует подмножество $X_1\subset X_0$ мощности
$N_1=\sqrt{N_0}$ вершин $x$, соединенных ребрами П с одной и той же вершиной $y_0\in Y$. В этом случае М
отмечает $y_0$.
\item{} Существует подмножество $X_1\subset X_0$ мощности
$N_1=\sqrt{N_0}$ вершин $x$, соединенных с различными вершинами $y\in Y$. В этом случае М проводит свои ребра
из $y$ в $x$ для всех пар $x\in X_1$ и $y\in Y$, соединенного с $x$ ребром П. Другими словами, М
дублирует ребра П, исходящие из вершин, входящих в $X_1$.
\end{itemize}

В будущем он будет рассматривать только вершины из $X_1$ вместо $X_0$.

Очевидно, третьей альтернативы не существует.

Описание первого этапа завершено.

Второй этап похож на первый. М ждет до тех пор, пока не появится по новому ребру П, выходящему из каждой
вершины $x\in X_1$. После этого появятся аналогичные две возможности и подмножество вершин $X_2\subset X_1$ мощности
$N_2=\sqrt{N_1}$.

Последующие этапы определяются аналогичным образом.

Число этапов ограничено числом $2^k$. Действительно, после $l$-ого этапа, появится множество вершин $X_l$ мощности
$N_l$ такое, что из каждой вершины $x\in X_l$ исходит как минимум $l$ ребер П. Таким образом, число этапов не
может превзойти $2^k$, в противном случае появится противоречие с ограничением $(1)$.

После последнего, $m$-го этапа, мощность $N_m$ множества $X_m$ останется не меньшей $2^{3k}$. Таким образом, найдется
достаточное число вершин $x\in X_m$ таких, что все исходящие из них ребра П либо продублированы М, либо
их противоположные концы отмечены М. Лемма доказана. $\Box$






Теорема~\ref{undiv-th} может быть дополнена следующими оценками
на длину и число слов~$x$, удовлетворяющих условию теоремы~\ref{undiv-th}.

\begin{theorem}\label{th-col}
Существует слово $x$ длины $3k 2^{2^k}$, удовлетворяющее условию
теоремы ~\ref{undiv-th}.

Более того, существует константа $c_1$ такая,
что для каждого     ``неделимого'' $x$ выполнено условие
$$
K(x)>2^{2^{k-c_1}}.
$$
Число таких $x$-ов конечно.
\end{theorem}



Зафиксируем произвольную константу $c_1$ и пусть $x$ такое, что
$$
K(x)<2^{2^{k-c_1}},
$$
удовлетворяет утверждению теоремы~\ref{undiv-th}. Зафиксируем любое рациональное число $1<\alpha<2$, например $\alpha=3/2$. Пусть
$$
A=\lceil \alpha^{\lceil \log_{\alpha} K(x) \rceil} \rceil.
$$
Тогда $A<\alpha K(x)$ и, так как $A$ однозначно задается целым числом $\lceil \log_{\alpha} K(x) \rceil$, то
\begin{equation}\label{A-ineq}
K(A)\le \log_2 \lceil \log_{\alpha} K(x) \rceil \le k-c_1-\log_2 \log_2 \alpha \le k,
\end{equation}
если $c_1$ достаточно велико. Зная $x$ и $A$, можно восстановить код $y$ для $x$ такой, что $K(x|y)<c_2$ и $K(x)\le
|y|\le A < \alpha K(x)$. Из (\ref{A-ineq}) следует, что $K(y|x)\le K(A)< k$ если $c_1$ достаточно велико. Разделим $y$
на две части равной длины. Очевидно, эти части окажутся нетривиальными.

Остается доказать, что число таких $x$ конечно. Пусть длина $x$ превосходит время, необходимое для перечисления всех
$y$ таких, что $K(y)<k+c$. Пусть также $K(x)> 4k$. Тогда зная $x$, мы знаем список всех $y$ таких, что $K(y)<k+c$.
Пусть $y_0$ -- первое в лексикографическом порядке слово, не входящее в этот список. Тогда $y_0$ обладает следующими
свойствами:

(1) $K(y_0)<2k$ так как число слов в списке не превосходит $2^{k+c}$, откуда следует, что $\ell(y_o)\le k+c+1$;

(2) $K(y_0)\ge k+c$;

(3) $K(x|y_0)\ge k+c$ из-за разности между сложностями $K(y_0)<2k$ и $K(x)>4k$;

(4) $K(y_0|x)< \log k$.

Получаем противоречие. $\Box$





\section{Точность положительного результата}\label{sectsmall}

\begin{theorem}\label{theorem3}
Существует константа $c$ такая, что выполнено следующее. Для любых целых положительных чисел $n$ и $d$ существует слово $x$, удовлетворяющее условиям: $K(x)\ge 3n$ и число слов $y$ таких, что
$$
K(y|x)\le n, \qquad n-d+2\log d+c\le K(x|y)\le n,
$$
не превосходит $2^d$.
\end{theorem}
\noindent {\bf Доказательство.} Рассмотрим игру, сформулированную в доказательстве Теоремы~\ref{undiv-th} (где $k=n$) и
конструкцию из доказательства Леммы~\ref{lemma-undiv}. Рассмотрим произвольную вершину $x\in X_m$ (напомним, что $X_m$
-- последнее из построенных множеств). Любая вершина $y$ соединенная с $x$ ребром Математика имеет номер $n_y$ своего
появления среди вершин, соединенных с $x$ ребром Математика.

Для доказательства теоремы, достаточно доказать следующее: любое интересующее нас слово (вершина) $y$, имеет те же
первые $n-d$ знаков в двоичной записи числа $n_y$, что и последняя вершина $y_{\text{last}}$, соединенная с $x$.

Докажем это. Предположим обратное. Нам надо доказать, что для любого более раннего $y$, выполнено $K(x|y)<n-d+2\log
d+c$ для некоторой константы $c$. Зная первые $n-d$ знаков (обозначим число, двоичной записью которого они являются через $m_0$) числа $n_{y_{\text{last}}}$ и $d$, мы
можем восстановить $n$. Зная $n$, можно запустить процесс $n$-й игры и дождаться $l_0=m_0 2^d$-го этапа. Тогда мы будем
знать, что $x$ уже соединен с нашим $y$ (по предположению). Во множестве $X_{l_0}$ может быть лишь один такой $x$.
Т.е. $m_0$ и $d$ задают $x$. Так мы приходим к противоречию. Теорема доказана. $\Box$

Из доказанной нами теоремы следует, что константа $c$ из формулировки Теоремы~\ref{theorem1-2} не может быть меньше,
чем $\Theta(\log m)$. А именно, верна следующая теорема.
\begin{theorem}\label{theorem4}
Пусть $n$ и $c$ -- произвольные положительные числа. Тогда найдется слово $x$ такое, что $K(x)\ge 3n$ и число
$m$ слов $y$, удовлетворяющих условию
$$
K(y|x)\le n,\ n-c\le K(x|y)\le n
$$
не превосходит $2^{2c}$.
\end{theorem}
\noindent {\bf Доказательство.}
Пусть $d=2c$ в Теореме~\ref{theorem3}.

Таким образом, $c\ge \frac{1}{2}\log m$. Отсюда следует, что слагаемое $5\log m$ в последнем неравенстве из
формулировки Теоремы~\ref{theorem1-2}, нельзя существенно уменьшить (его нижняя граница равна $\frac{1}{2}\log m$).$\Box$


Наконец, переформулируем основное утверждение данного раздела еще раз, с полиномиальной оценкой на число слов.

\begin{corollary}\label{corollary4}
Пусть $N$ и $n$ -- произвольные положительные числа.
Существует константа $c$ и слово $x$ такие, что $K(x)\ge N$
и число слов $y$ удовлетворяющих условию
$$
K(y|x)\le n, \qquad n-\log n\le K(x|y)\le n
$$
не превосходит $n^2$.
\end{corollary}












\section{Еще одна попытка обобщить основной результат}\label{attempt}

В этом разделе мы докажем невозможность обобщения результата
Теоремы~\ref{theorem1-2} в другом направлении.
Сначала, заметим, что Теорема~\ref{theorem0} может быть обобщена
следующим образом.

\begin{theorem}\label{theorem10}
Пусть число $n$ и слово $x_0$ такие, что $K(x_0)\ge n$, фиксированы.
Тогда найдутся слова $x_1$ и $x_2$ такие, что
\begin{gather*}
|K(x_i|x_j)-n|\le 3\log K(x_0), i,j\in \{ 0,1,2 \}, i\neq j\\
|K(x_i|x_j,x_k)-n|\le 3\log K(x_0), i,j,k\in \{ 0,1,2 \}, i\neq j\neq k,
i\neq k.
\end{gather*}
Эти неравенства выполнены с точностью до аддитивной константы,
зависящей только от выбора универсального языка программирования.
\end{theorem}
\noindent {\bf Доказательство.} Доказательство этой теоремы аналогично
доказательству Теоремы~\ref{theorem0}. $\Box$

Встает естественный вопрос: верно ли что Теорема~\ref{theorem1-2}
также может быть обобщена аналогичным образом?
Следующая Теорема~\ref{impos-th} дает отрицательный ответ на
этот вопрос. Этот результат был получен ранее независимо от Теоремы~\ref{undiv-th} и
опубликован в \cite{vyugin-ppi}, здесь же мы приводим более простое его доказательство.


\begin{theorem}\label{impos-th}
Существует константа $c$, для которой выполнено следующее.
Пусть $n$ и $d$ -- произвольные целые числа.
Существует слово $x_0$ такое, что $K(x_0)\ge n+d$ и нет слов
$x_1$ и $x_2$, удовлетворяющих следующим неравенствам:
\begin{gather*}
K(x_i|x_0)\le n+d, i\in \{ 1,2 \},\\
K(x_0|x_i)>d+2\log n +c, i\in \{ 1,2 \},\\
K(x_2|x_0,x_1)>n+2\log d.
\end{gather*}
\end{theorem}

Заметим, что в доказательстве Теоремы~\ref{theorem1-2} при $m=2$, выполнено
приблизительное равенство $K(x_2|x_0,x_1)\approx 0$. Поэтому конструкция из этого доказательства
здесь неприменима.

\noindent {\bf Доказательство Теоремы~\ref{impos-th}.} Рассмотрим игру из доказательства Теоремы~\ref{undiv-th} (где
$k=n+d$) и конструкцию из доказательства Леммы~\ref{lemma-undiv}. Рассмотрим любую вершину $x_0\in X_m$ ($X_m$ --
последнее множество из построенных в доказательстве Леммы~\ref{lemma-undiv}). Любая вершина $y$, соединенная с $x$
ребром Математика имеет свой номер $n_y$ появления среди таких вершин.

Для доказательства теоремы, достаточно доказать следующее:
любые интересующие нас $x_1$ или $x_2$ имеют те же первые
$d$ знаков номеров $n_{x_1}$ или $n_{x_2}$, что и последний
из $y$, соединенных с $x$.

Докажем это. Предположим противное. Нам надо доказать, что для всякого более раннего $x_1$, выполнено
$K(x_0|x_1)<d+2\log n$. Зная первые $d$ знаков (обозначим число, двоичной записью которого они являются через $m_0$) $y$ появившегося последним, зная $x_1$ и
$n-d$, мы можем восстановить $n$. Зная $n$, можно запустить процесс $n$-й игры и дождаться, $l_0=m_0 2^{n-d}$-го этапа.
Тогда мы будем знать, что $x_0$ уже соединен с нашим $x_1$. Во множестве $X_{l_0}$ есть только один такой $x_0$. Мы
пришли к противоречию. Такое же рассуждение проходит и для $x_2$.

Легко видеть, что зная $x_0$, $x_1$, $d$ и последние $n$
битов $x_2$, можно восстановить $x_2$. То есть
$K(x_2|x_0,x_1)<n+2\log d$.
Теорема доказана.
$\Box$


\bigskip

Авторы выражают благодарность А.~Шеню, Н.~К.~Верещагину за полезные обсуждения, а также всем участникам
колмогоровского семинара по сложности вычислений за внимание.














\begin{thebibliography}{10}

\bibitem{mvyugin}

Vyugin M. Information Distance and Conditional
Complexities. // Theoretical Computer Science. 2002. V.271. P.145-150.

\bibitem{vyugin-ppi}
{\it Вьюгин~М.В.} {Системы слов с большой взаимной сложностью. } // Проблемы передачи информации. 2003. Т.~39, Вып. 4,
С. 88-92.

\bibitem{kolmogorov}

Колмогоров А.Н. Три подхода к определению понятия
``количество информации''. // Пробл. передачи информ. 1965. Т.1. N1 С.3-11.

\bibitem{li-vitanyi}

Li M., Vit\'anyi P. An Introduction to Kolmogorov
Complexity and Its Applications. Springer, 1997.


%\bibitem{muchnikan}
%{\it Muchnik An.A.}
%{ Conditional complexity and codes.} //
%Theoretical Computer Science. 2002. V.~ 271(1-2), P.~97-109.

\bibitem{vervyu}

N.~Vereshchagin, M.~Vyugin. Independent minimum length
programs to translate between given strings. // IEEE Conference
on Computational Complexity, 2000.


%\bibitem{BGLVZ}
%C.H.~Bennett, P.~G\'acs, M.~Li, P.M.B.~Vit\'anyi, and W.~Zurek.
%Information distance. // IEEE Transactions on Information
%Theory, 1998, V.44, No.~4, P.1407--1423.

\end{thebibliography}


\end{document}
