%%
%% An.A.Muchnik
%% version 2.11.2002
%%
%% codepage 866
%% Russified LaTeX2e, based on LaTeX2e 2001/06/01
%% Document Class: article 2001/04/21 v1.4e
%% Package: amsmath 2000/07/18 v2.13
%% Package: amssymb 1995/02/01 v2.2a
%% Package: amsthm 2000/10/26 v2.08
%% Package: russcorr 1996/03/24 (by S.Lvovski)
%%


\documentclass[12pt,draft]{article}

\usepackage{amsmath,amssymb,amsthm}
\usepackage[indentheadings]{russcorr}
%% babel staff
%\usepackage[T2A]{fontenc}
%\usepackage[koi8-r]{inputenc}
%\usepackage[russian]{babel}


\newtheorem*{thm}{Теорема}
\renewcommand{\proofname}{Доказательство}


\newcommand*{\pair}[1]{\langle #1\rangle}
\newcommand*{\perems}[2]{#1_1,\ldots,#1_{#2}}
\newcommand*{\gr}[1]{\mathbf{#1}}

\renewcommand{\le}{\leqslant}
\renewcommand{\ge}{\geqslant}

\hfuzz=0.5pt
\tolerance=300

\author{Андрей Мучник\thanks{
        Институт новых технологий,
        109004, Москва, ул. Нижняя Радищевская, 10.
        \mbox{E-mail}:~muchnik@lpcs.math.msu.ru,
        fax:~(095)9156963.
        Работа выполнена при поддержке
        Российского Фонда Фундаментальных Исследований,
        гранты N~01-01-00505, N~02-01-22001.}
       }

\title{О сложности перехода
от перечислимого задания конечной структуры
к е\"е явному заданию
}

\date{}

\begin{document}
\maketitle

Пусть фиксирован оптимальный в смысле~\cite{3appr}
язык программирования.
Под \emph{энтропией} конструктивного объекта
мы будем понимать длину кратчайшей программы,
выдающей этот объект на пустом входе.
Рассмотрим множество $S$
конструктивных объектов мощности $k$
перечисляемое программой длины
$\alpha \ll \log k$
(здесь и далее логарифмы берутся
по основанию $2$).
Как известно, в некоторых случаях
энтропия списка элементов множества $S$
как конструктивного объекта
может быть больше $\log k$.
(То есть, сложность явного задания
конечного множества
может быть гораздо больше сложности
его перечисления.)
Тем не менее, просто строится
другой список $L$ мощности
$O(k\cdot 4^{\alpha})$
и энтропии не больше
$\log\log k+O(1)$,
в котором для каждого элемента $S$
есть \emph{двойник}.
Это значит, что
$$
\forall x\in S\,\exists y\in L\quad
[K(x|y) \le O(1)]\land
[K(y|x) \le \alpha + O(1)]\,,
$$
где $K(x|y)$~--- условная энтропия
$x$ при известном $y$,
введ\"енная в~\cite{3appr}.
Список $L$,
обладающий указанными свойствами,
мы будем называть \emph{напарником} $S$.

А.~Ромащенко выдвинул гипотезу,
что если некоторое отношение $R$
на множестве $S$ перечисляется короткой программой,
то у полученной структуры тоже есть напарник
(при естественном обобщении понятия напарника).
Более точно, предположение состояло в том,
что существует список $L$ и отношение
$T$ на его элементах, такие что
\begin{enumerate}
\item мощность $L$ не во много раз больше мощности $S$,
      мощность $T$ не во много раз больше мощности $R$;
\item энтропия $\pair{L,T}$
      не намного больше длины $\alpha$ программы,
      перечисляющей множества
      $S$, $R$;
\item $\forall \perems{x}{i}\in S\:
       \exists \perems{y}{i}\in L\\{} \quad
      [R(\perems {x}{i})\Rightarrow T(\perems{y}{i})]
      \:\land\:
      [\forall j$ $x_j$~--- двойник $y_j]$.
\end{enumerate}
Приводимая ниже теорема опровергает
сформулированную гипотезу уже для $i=2$.

Выражение $x\sim y$
будет сокращением для
$$
[K(x|y) < C\log n]\land [K(y|x) < C\log n]\,.
$$
\begin{thm}
 Пусть число $n$ достаточно велико
 по сравнению с числом $C$.
 Рассмотрим
 $S$~--- множество двоичных слов длины $3n$~---
 и двуместное отношение $R$, содержащее те пары
 $\pair{x,u}$ элементов $S$, для которых
 $K(\pair{x,u}) < 5n$.
 (Заметим, что $|R|=2^{5n-O(1)}$.)
 Тогда не существует списка $L$
 и двуместного отношения $T$ на его элементах,
 таких что
\begin{enumerate}
\item\label{th:1}
 $|L| < |S|\cdot n^C$,  $|T| < 2^{5n}\cdot n^C$;
\item\label{th:2}
 $K(\pair{L,T}) < C\log n$;
\item\label{th:3}
      $\forall x,u\in S\:\exists y,v\in L\:\:
      [R(x,u)\Rightarrow T(y,v)]\land
      [x\sim y]\land [u\sim v]$.
\end{enumerate}
\end{thm}
\begin{proof}
По $n$ и $C$
мы определим алгоритм перечисления
некоторого множества $A$ пар двоичных слов длины $3n$.
Мощность $A$ будет не больше $2^{4n}n^C$,
поэтому энтропия каждого элемента $A$
будет не больше $4n+O(\log n) < 5n$.
Следовательно, $A\subseteq R$.
Нам удобно интерпретировать множество $A$
как двудольный граф $\gr A$.

Рассмотрим перечисление всех пар $\pair{L,T}$,
удовлетворяющих пунктам~\ref{th:1} и~\ref{th:2}
из условия теоремы.
За сч\"ет пункта~\ref{th:2}
количество таких пар меньше $n^C$.
При появлении очередной пары
мы построим соответствующий ей
двудольный граф $\gr B$.
В качестве долей $\gr B$ используются
две копии множества $S$.
Степень ветвления каждой вершины
левой доли $\gr B$ будет не больше $2^n$.
Множество р\"ебер графа $\gr A$
будет объединением
множеств р\"ебер всех графов $\gr B$.
Для каждой пары $\pair{L,T}$
в соответствующем графе $\gr B$ найд\"ется
такое ребро $\pair{x,u}$, что
$\forall y\sim x\mspace{12mu}
 \forall v\sim u\quad \neg T(y,v)$.
Поэтому $\pair{L,T}$ заведомо не будет напарником
$\pair{S,R}$.

Теперь определим как паре $\pair{L,T}$
(которую мы будем интерпретировать как
двудольный граф $\gr L$)
сопоставляется граф $\gr B$.
Рассмотрим подмножество $L'$ левой доли $\gr L$,
состоящее из вершин со степенью ветвления
больше $2^{2n}n^{3C}$.
Понятно, что $|L'| < |T|/2^{2n}n^{3C} < 2^{3n}/n^{2C}$.
\emph{Отношением сходства}
будем называть произвольное
множество $D \subseteq S\times L$,
для которого выполнено
$\forall x\quad\bigl|\{y| D(x,y)\}\bigr| < n^C$
и
$\forall y\quad\bigl|\{x| D(x,y)\}\bigr| < n^C$.
Введ\"енное ранее отношение $\sim$,
ограниченное на $S\times L$,
является отношением сходства.
Количество всех отношений сходства не превышает
$$
|L|^{2^{3n}\cdot n^C} \le 2^{2^{3n+O(\log n)}}\,.
$$
Пусть $E$~--- множество всех двоичных слов длины $n$.
Рассмотрим равномерное вероятностное
распределение на множестве
всех функций из $S\times E$ в $S$.
Мы хотим показать, что существует функция
$F\colon S\times E\to S$,
для которой выполнено событие
\begin{multline*}
\forall D\text{~--- отношения сходства }
\exists z\in E\: \exists x,u\in S\\
F(x,z)=u\:\land\: \forall y,v\in L\:
[D(x,y)\land D(u,v) \Rightarrow \neg T(y,v)]\,.
\end{multline*}
Для этого мы докажем, что вероятность
противоположного события
(обозначим его $\mathfrak{B}$)
строго меньше $1$.
Так как рассматриваемое событие разрешимо
равномерно по $\gr L$,
то функцию $F$ можно будет найти перебором.
Ясно, что в качестве множества р\"ебер графа $\gr B$
можно будет взять
$$
\{\pair{x,u}\mid \exists z\in E\: F(x,z)=u\}\,.
$$

Фиксируем отношение сходства $D$.
Обозначим через $S'$ множество элементов $S$,
которые $D$-сходны с элементами $L'$.
Очевидно, что
$|S'| \le |L'|\cdot n^c < |S|/2$.
Пусть $z\in E$ и $x$~--- вершина левой доли $\gr B$,
не принадлежащая $S'$.
Оценим сверху вероятность
следующего события $\mathfrak{D}$:
$$
\forall y,v\in L\quad
[D(x,y)\land D(F(x,z),v) \Rightarrow \neg T(y,v)]\,.
$$
Для этого рассмотрим в правой доле $\gr B$
следующее подмножество
$$
\{u\mid \exists y,v\in L\:\: D(x,y)\land T(y,v)\land D(u,v)\}\,.
$$
Его мощность меньше
$n^C\cdot 2^{2n}n^{3C}\cdot n^C < |S|/2$.
Отсюда следует, что вероятность $\mathfrak{D}$
меньше $1/2$.

Вероятность события $\mathfrak{B}$
не превышает количества отношений сходства,
умноженного на вероятность события
$\mathfrak{D}$ в степени
$\lvert E\times (S\setminus S')\rvert$.
То есть, интересующая нас вероятность меньше
$$
 2^{2^{3n+O(\log n)}}\cdot 2^{-2^n\cdot 2^{3n-1}}\,,
$$
что при больших $n$
строго меньше $1$.

Теорема доказана.
\end{proof}

Автор признателен
Андрею Евгеньевичу Ромащенко
за постановку вопроса и
полезные обсуждения.
Большую помощь оказал
Алексей Вячеславович Чернов
при подготовке текста к публикации,
за что автор ему очень благодарен.

\begin{thebibliography}{9}
\bibitem{3appr} А.~Н.~Колмогоров.
Три подхода к определению
понятия \glqq количество информации\grqq.
{\it Проблемы передачи информации},
т.~1 (1965), N~1, с.~3\nobreakdash--11.
\end{thebibliography}

\end{document}
