\documentclass[12pt]{article}
\usepackage{amsmath,amstext,amssymb}
\DeclareMathOperator{\poly}{poly}
\newtheorem{theorem}{�������}
\newtheorem{lemma}{�����}

\begin{document}

\title{�������� ��������� � ���� (�� ��.\,�.\,�������)}

\section{��������}

����� ���� ��� ������������ �������� ����� $x$ � $y$. ��������
�������������� ���������� $K(x|y)$ �����~$x$ ������������
�����~$y$ �������� ����� ���������� ���������, ������� ���������
$y$ � $x$. ������ �������� $K(x|y)$ ������� �� ������ �������
������ ��������, ������ �������� ��� �������: ���������
������������ ����������� (�������� ����������� �����������,
���������� ��������� � ������) ���������� �� ����� ��� ��
$O(\log n)$ ��� ���� ����� �� �����~$n$. �� ����� ������������
�������� ������� $O(\log n)$, ��� ��� ��� �� �����, ����� ������
����������� ������������.

����� ���� �� ��������, ��� ���������� ��������� ��������
����������, ������� ���� � $x$ � ����������� � $y$. ������
�������� �� ��� ������: ���������, ����������� $x$ � $y$, �����
�������� ������� ����������, ��� ���������� ������� ������.
����� $x$ � $y$ --- ��� ���������� ��������� ��������� �����
����� $n$. ���������� ��� ���������, ����������� $y$ � $x$:
������ �� ��� ���������� ���� � �������� $x$; ������ �� �����
$t$ ���� ����� $t\oplus p$, ��� $\oplus$ ������������ ���������
�������� �� ������~$2$, � $p$ ��������� ���, ��� $y\oplus t=x$
(������� �������, $p=x\oplus y$). ��� ��� ��������� �� �����
������ ������ (� ��� ������, ��� ����� $x$ � $p$, �� ��������,
�� ����� ����� ����������).

��.\,�.\,������ �������, ��� ��� ����� $x$ � $y$ ���ģ���
��������� $p$, ����������� $y$ � $x$, ����� ������� ������ �
�������� (�� ���� � $K(x|y)$) � ������� ������ ������������ $x$
(�� ���� $K(p|x)\approx 0$). ������ ������������ �
�������������� ����� ���������� ���������� ����. (� �����
������� ���� ��������� �������� ������ ���������, �� �� ������.)

\section{��������� � ����}

����� ���� �� ��������� ������ ����������������, �� �����
�������� �� � ����������, � � �����. ����� $p$ �� ����� ��������
\emph{�����} $x$ \emph{��� ���������} $y$, ���� ��������
��������� ����� $x$ ��� ��������� $y$ � $p$ ������ � ����
(������ ������� ����� ����������� � �������������). �����
��������, ���

\begin{itemize}

\item ���� $p$ ���� ��� $x$ ��� ��������� $y$, �� ��������� $p$
      (� ��� ����� ����� $p$) �� ����� ���� ������ ������ $K(x|y)$;

\item ��� ����� $x$ � $y$ ���������� ����� $p$. ���������� �����
      $x$ ��� ��������� $y$ � ������� ����� �������� $K(x|y)$.

\end{itemize}

������ ������������ ������:

\begin{itemize}

\item $K(p)\ge K(x|y) - K(x|y,p) + O(\log n)$ ��� ����� ���� $x,y,p$
      ����� �� �����~$n$;

\item ��� ����� $x$ � $y$ ����� �� ����� $n$ ���ģ��� ����� $p$,
      ����� �� ����� $K(x|y)+O(\log n)$, ��� ��������
      $K(x|y,p)=O(\log n)$

\end{itemize}

� ����� ����, ������ ����������� ���������� ���������, ���� ����������
��� ���:
        $$
K(x|y) \le K(x|y,p)+K(p)+O(\log n)
        $$
(�� ��������� ��� $p$ � ���������, ������ $x$ ��� ��������� $y$ � $p$,
����� ��������� ���������, ������ $x$ ��� ��������� $y$; ���������
������� �� ����������� ����� ��������� �� ����������� $O(\log n)$).

� ������ �������, ���� � �������� $p$ ����� ����������
���������, ����������� $y$ � $x$, �� $|p|=K(x|y)$ �� ����������
� $K(x|y,p)=O(\log n)$, ��������� �� $y$ � $p$ ����� ��������
$x$, �������� $p$ � $y$.

\section{������� �������}

�������, ��� ���� ����� $x$ �������� ����� $x$ ��� (�����)
��������� $y$. ������� ����� ���� ����� $x$ ��� ��������� $y$
�������� ���� ����, ������� ������������ $x$. �����������, ���
��� �������� ����� �������� � ����������� ����������� �����:
����� ����� $x$ ��� ��������� $y$ ���� ��� ����� ��������
$K(x|y)$, ������� ������������~$x$.

(������� � �������, ��� ���� �������� ���������� � ������
��� ����������� �����, ������� ������������ ���� $(x,y)$,
�� ��� �����: ����� ���������� ��� ��������� ����� $K(x|y)$
� ������ ����� ��� ���������, ����������� $y$ � $x$; ������
��������� � ����� ������� �����, ��� ��� ��� ţ �������
���������� ������� $x$, $y$ � �������� $K(x|y)$.)

\begin{theorem}

����� $x$ � $y$~--- ������������ ����� ����� �� ����� $n$. �����
���ģ��� �����~$p$ ����� $K(x|y)+O(\log n)$, ��� ��������
$K(p|x)=O(\log n)$ � $K(x|p,y)=O(\log n)$.

\end{theorem}

\noindent
(��������� � $O(\log n)$-������������ �� ������� �� $n$, $x$ �
$y$.)

\section{����� ��������������}

������� ������ �������� ���� ��������������. ����� $X$~---
��������� ���� ���� ����� �� ����� ��� $n$. ��������� ���������
$K(x|y)$ ����� $p$. ���������� ��������� $P$ ���� ���� ����� ��
�����~$m$. �� ����� ��������� \�� �����������\��, ��� ����
���������� ���-������� $\varkappa\colon X\to P$. (������ �����
������� ������� � ������ ���������� ��� ��������, �� ������
����.) � �������� �������� ���� ����� $x$ ��� ���������~$y$
����� ��������� ���-�������� $p=\varkappa(x)$ �����~$x$. ���
������ ������������ $x$ (���� ���� ���-������� $\varkappa$
������). �� ��� ������������ $x$, ���� $p=\varkappa(x)$ � $y$?
����� ���������� ��� ����� $x'$, � ������� $K(x'|y)\le m$
(����������� �������� ��� ��������� ����� �� �����~$m$ � �����~$y$)
� ��������� $\varkappa(x')$. ��������� ���� ����� $x'$ �� ���������
$X_y$. ���� ��� ����ڣ� � � $X_y$ ���� ������ ���� ����� $x'$, ���
�������� $\varkappa(x')=p$ (�� ���� ���� $x$), �� ���������
������� ���� ��� ������ ���� ��� $x$, ��� ��� ��������� $x$
������������ $y$ � $p$ ����. �� ��� ��������, ��� ����� $x'$
������ ����?

\section{��� �����������}

����� ���� ���� ���� ����������, ��� ���ģ��� ����� �� �������
�ң� �����.

\subsection*{��������� ���-�������} ��-������, �� �����
������������� �� ���� ���-������� $\varkappa$, � ���������
$\varkappa_1,\dots,\varkappa_N$ �� $N$ ���-�������. ���� ��
����� ($N$) ���������� ��������� �� $n$, �� �������� ����� ��
��� � �����~$x$ ����� ������ ������������~$x$ (� �������������,
��� ���� ��������� �������)~--- � ����� ����, ��� ���������
$\varkappa_i(x)$ ���������� ������� $i$, ��� ���� ���������
$\log N=\log \poly(n)=O(\log n)$ �����. ���� ���� �� ���� ��
������� $\varkappa_i$ �������� ������������ ���~$x$ � ���������
$X_y$ (�� ���� $\varkappa_i(x)\ne\varkappa(x')$ ��� ������
$x'\in X_y$), �� ����� ��� ������ ����������: ��� ��������������
$x$ �� $y$ � $p=\varkappa_i(x)$ ���������� ����� $m$ � $i$
(������ ������ ��������� ���-�������, ������� �� ������������
�������).

\subsection*{��������� ����������}
������� �ݣ ���� ���. �������, ��� ��� �� �����������, �����
������� $x'\in X_y$, ��� �������� $\varkappa_i(x')=p$, ��� �����
����. ����������, ����� ����� ��������� ���� �� ������� �����
(�� ����� ������ ���� ���������� ��������� ��~$n$). � �����
����, ���� ��� ���, �� ��� �������������� $x$ �� $y$ � $p$ �����
������� ������������� ������� ���� ���������� ����� $x$ �
������� ���� $x'$, � ������� $\varkappa_i(x')=p$ (� �������
��������� ��� ������������).

\subsection*{�� ��� $x\in X_y$ ����� ���� ��������} ������ ��
�����, ��� ���������� ��������� ������� ��������� ���-�������
��������������� (��~$n$) ������� � ����� ���������: ��� ������
�������� $x\in X_y$ (��������: ��� ��������, ��� $K(x|y)\le m$)
���ģ��� ���-������� $\varkappa_i$, ��� ������� ����������
$x'\in X_y$ � $\varkappa_i(x)=\varkappa_i(x')$ ����������
��������� �� $n$. ������ � ��������� ������� ������� �
���������: ����������, ����� ��� �������� ���� ��������� ���
���� $x\in X_y$, ����� ������������ ��������� �� �����. � �����
����, ����ף� �� $x\in X_y$, ��� ������� ��� �� ���������, \��
�������\��\ (� ��������� --- \�� ��������\��). ��������� ������
$x$ (���, ������� ����������� ����� ��������� $\varkappa_i$ �
������� ������ ������ ���� �. $X_y$) ����� �����������,
����~$y$. ������� ���� ������ $x$ �������, �� �� ��������
��������� ����� ������ $m$ (� �� ������������� $K(x|y)=m$,
������, ����������� ��� $x$ ����� �������).

\section{������ ������� ���-�������}

����� ���� ���� ������� ����� ���������, ��� ���������
���-������� � ������������� ��� ���������� ����������. ������
���������� ��� ��������� � ���� ����������� �����. ����� �����
����� �� $X$, ������\~--- ����� ��~$P$ (����� �������, �����
�������� $2^n$ ����, � ������ �������� $2^m$). ������ �����
$x\in X$ �������� $N$ ң����� � ��� ���-����������
$\varkappa_1(x),\dots,\varkappa_N(x)$. ��� ���������� �����
����� �����, ������� ���������, ���� ����� �������� ���� �������
�� $X_y$ ��� ���������� $y$. ��� �������, ����� ������� �� $X_y$
����� �������� (� ��������� ���� ������)? ���� � �����-��
������� $x$ ����� ���� ����� $p$, � �������� ���� ������� �����
(� ������������ �� $X_y$ �����), �� ����� ������� ��������
������: $p$ �������� ���-���������, ������� ����������� ���� �
���������� ����� ��������� ��������� $X_y$. (���� ������ ������,
��������� �� �� �������, ��������� ����� ������ ���-�������
�������� ������ �����. ���������
$\varkappa_i(x)=\varkappa_j(x')$ ��� $i\ne j$ ��� ����� ��
������, �� ������������ ������ ����ޣ�� ����� �� ���������.)

����, � ����� �� $X_y\times P$ �� �������� ������ ���-��������
(������� ������, ������� ����� ������� �����). ������� ����� �����
�������� �������, ���� ���� �� ���� ţ ����� ������ �����
(����� ���� ������� �����). �������, ��� ������� ��� �� ���
(��� ������ ������ ������), �� ����� �������� \�� ��������\��;
��� ����, ����� �� ���� �������. (��� �� ��� ��������, �����
������� ������ ����� ���� � �������, �� �� ����� �� ���������.)

����� ���� �����. ����� ���� (������, � $X\times P$) ��������
��������� ���� ����������: ��� ������� ��������� $S\subset X$
�������� ��������� ������ $2^m$ ��������� $S'$ ���� ������� ����
������ �� ���������~$S$ �������� �� ������ ���������, ���~$S$.
��� ��������, ���������, ���������� � ��� ����������� ����� ��
$X_y\times P$. ��� �����������, ��� ���� ������ ������ ������
����, �� � ������� ������ ����� ���� (��� ������ �������
������~--- ������). � ����� ������ ������ ������ ����� �������
������: ��� �� ����������� ������ ����� ������ �����, ��̣�����
�� ������� ������ ������� ������ (������� ���������� ������ ��
����������� ������ �������). ����� ����� ������ ����� �� ����
$|X_y|\times N$ (�� ������ �� $|X_y|$ ������ ����� ������� $N$
ң���).

�������� �������, ������ ��ң��� ��������� ���-������� ��
��������� ����������. �� ���������� (������������), ��� �����
��������� ����������, � ����� �������, ��� ��� ������ $n$ � $m$
����� ��������� ��� ������ ������� �� �������, ���� ��
����������� ����� � ������ ���������. ������ �� ����� �������
�������������� ������������ �� $n$ � $n$ � ������ �����
��������� $O(\log n)$.

\section{������ ������������}

\begin{lemma}

����� $m$ � $n$~--- ����� ������������� �����, ���ޣ� $m\le n$.
����� $X$ � $P$~--- �������� ��������� �������� $2^n$ � $2^m$
��������������. ����� ����� ������������� ����� $N$ � $u$ ������,
���
        $$
\frac{u}{2^m} < 2^{-(m+n)/N}
        $$
����� ���������� ����� �� $N$ �������
        $$
\varkappa_1,\dots\varkappa_N\colon X \to P
        $$
� ����� ���������: ��� ������� ��������� $U\subset X$ �������
$u$ ��������� ���� $\varkappa_i(u)$ ��� ���� $u\in U$ � ����
$i\in\{1,\dots,N\}$ �������� �� ����� $u$ ���������.

\end{lemma}

�������������� �����. �������, ��� ��� ��������� �������
$\varkappa_1,\dots,\varkappa_N$ ��������� �������� ��������� �
������������� ������������. � ����� ����, ������� �� �����
$2^{nu}$ ��������� ��������~$U$: �� ������ �� $u$ ����� �� �����
������� ����� �� $2^n$ ���������. (��� ������ � ������� �������,
��� ��� �� �� ��������� ������� ������ � �����������
����������.)

��� �������������� $U$ ���������� ����������� ����, ��� ���
�������� $\varkappa_i(u)$ (��� ���� $u\in U$ � ��� ���� $i$)
������� � ��������� ��������� $V$ �� $u-1$ ���������. �����
����� �������� ������ $2^{mu}$, � ��� ������ ������ ���������
����������� ������� � ���� ������ $(u/2^m)^{Nu}$ (���������
�������� $N$ ��������� ������� � $u$ ��������� ������ ����������
� ��� ������� �� ��� ����������� ������� � $V$ ������ $u/2^m$).

����� �������, ��������� ����������� ���������������� ������
������
        $$
2^{mu}\cdot 2^{nu}\cdot \left(\frac {u}{2^m}\right)^{Nu}
        $$
� �����, ����� ��� ����� ���� ������ �������. ��������
������ �������~$u$, ����� ��������� �������������� ���
��� �������� ������� �� �����. (����� �������������� �����.)

�� ����� ������������ �����, ���
        $$
\frac{u}{2^m} < 1/n.
        $$
����� ���������� ����� $N=O(n\log n)$, ��� ��� ����� ���������
���-������� ����� �������� ������ $n$ � ������ ��� ��������
����� �� ��� ���������� $O(\log n)$ ����� (���� ������� ��������
$m$ � $n$, � ����� ���������� ����� ���-�������).

\section{������ ����� �������}

�����ģ� ������ � ������� ����� ������ � ������� ������.
��������, ��� �� ������������� ����� $x$ � $y$ ����� �� �����
$n$, ��� ������� $K(x|y)=m$, ����� $X$ �� ���������� ���������
���� ���� ����� �� ������~$n$, ����� $P$~--- ��������� ���� ����
����� �� ������ $m$ (��� ����� ������������ ��� ���-��������).

��������� $X$ �������� �������� $2^n$ ��������� (������,
$2\cdot2^n-1$, �� �� ��������֣� ���� ��������~--- ��������
���������, ��� ��� ���� ��� ������); ��������� $P$~--- ��������
$2^m$ ���������.

��� ������ $x$ � $y$ �� �������� ���-�������� $p\in P$ ������,
���� ��� ����� ����� $n^c$ ������� � ��������� $X_y$ ���� ����
����� �� ����� $n$, ������� ��������� �� ����� $m$ ������������
$y$. (������ �������� ���������� ������� ��������� $c$ ��
������� �������.) ��� �� ������, ����� ������ �������� ������
        $$
|X_y|\cdot N /n^c <
   2\cdot 2^m\cdot n/n^c =
     \left(\frac{2}{n^{c-1}}\right)\cdot 2^m.
        $$
��������� ������ ����� ����� ����������� ����� $u$. ��� $c>2$
��������� $u/2^m$ ���� $O(1/n)$, � ����� ��������� ����� �
$N=O(n/\log n)$, ��� ��� �ӣ ��������. �� ����� ����� �������
������ ����� ����� ������ $u$ (����� $u$ ������� ������ �� �����
�� ����� ������ ������ �������, ��������� ����� ������ ������
������ ������~$u$). �������������, ��������� ����� ������� �������
��� ���������~$y$ �� �����������
        $$
O(\log n)+\log\left(\frac{2}{n^{c-1}}\cdot 2^m\right) =
            O(\log n) +m - (c-1)\log n
        $$
(��� ������� ������� ������� ���� ������� $n$ � $m$, ����� ����
����������� ����� ���-������� � ��������� ������� ����� �������
� ������������ ���� ������� ��� �������~$y$ ������). �����, ���
��� ���������� ������� $c$ (�� ����� ���� ���������� �����,
������, $c=4$) ��� ��������� ������ $m$ � ������ ��������
������� $x$ �� ����� ���� �������. ��� ������, ��� � �ţ ����
������� ����� $p$. ����� $K(p|x)=O(\log n)$ (���������� �������
���-�������, ������ $p$ �� $x$) � $K(x|y,p)=O(\log n)$
(�������~$x$ �������� ����� �� �� ����� ��� $n^c$ �������
������� $p$ � $X_y$, ��� ��� ��� �������� $x$ ��� ���������~$y$
�~$p$ ����������� ������� $n$, $m$ � ���������� ����� �������
$x$ � ������ �������, ������� ��������� ��������� �� $n$).

������� ������� ��������.

\end{document}
