\documentclass[a4paper,12pt]{article}
\usepackage{amsmath,amssymb,amsthm}
\pdfpkresolution=600
\usepackage{russcorr,russadd}
\usepackage{zqtimes}
%\usepackage[koi8-r]{inputenc}
%\usepackage[T2A]{fontenc}
%\usepackage[russian]{babel}
\usepackage{fullpage}
\usepackage{graphicx}
\def\le{\leqslant}
\def\ge{\geqslant}

\newtheorem{thm}{�������}
\newtheorem*{lem}{�����}
\DeclareMathOperator{\KS}{\textit{KS\,}}
\DeclareMathOperator{\KP}{\textit{KP\,}}
\DeclareMathOperator{\poly}{\mathrm{poly}}

\begin{document}

\title{�������������� ��������� � ������������}
\author{��.\,�.\,������\thanks{%
        � ������ ���������� ����� ����������� ��.\,�.\,�������
        (1958--2007), ������������ �� 11~����� � 8~������
        2003~���� �� �������������� �������� �������
        �������������� ������ � ������ ���������� ��������\�
        ��������������� ���������� ���; ������������ ����
        ����������� ��������� ���������� �������
        ��.\,�.\,������� � �.\,�.\,��ͣ���� �� �������� �
        Dagstuhl (Seminar~03181, 27.04.2003--03.05.2003). �����
        ����������� �.\,������ � �.\,���� � 2008--2009~�����.}
}

\date{}

\maketitle

\begin{abstract}
        %
� ����� ������ �������������� ��������� ��������������� ������ �
���������� ���������, ������� �������� ������ ����������
���������� � �������� ������� � ����������� �� ����, �����
�������������� ����������� ����������� ����������.
        %
\end{abstract}

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

� ���� ������� �� ��� ������ ���� $a$ � $b$ (��� ���������
������������) �������� ����� $f$, ������� ��������� �������� $b$
�� $a$, �� ���� �� ���� (��� $a$) �� �������� ����������
������������~$b$, � ����� ���������� ��������� ��������� ����
������.

\subsection*{����������� � ������������� ���������}

���Σ� � ��������� ����� ���������, ������������ ����������
������ � ����� ������ �������������� ��������� ���������
��������. ����� $X$ --- ��������� ��������� (��������) ����, �
$y$ --- �����. ����� ����� ���������� $\KS(X\to y)$ ���
����������� ����� ���������, ������� ���� $y$ �� ����� �����
$x$ �� $X$. (��� ������, �� ��������� ��������� �����������
������ ������ ��������; ����� ����� ������ ����������� �����
�������� � ����������� ���������.) ��������, ���
    $$
\KS(X\to y) \ge \max_{x\in X} \KS(y|x)
    $$
(���� ��������� $p$ ������� ��� ���� $x\in X$, �� ��� �������
��� ������ �� ���), �� �������� ����� �� ������ � ����� �����
����� ���� ����������� ������ ������. ����� �������, ��� \��
�����������\��\ ��������� ������ $X\to y$ (����� �����) �����
���� ����������� ������ \�� �������������\��.

����� ��������� � ����, ����ͣ� � �������� $y$ ����������� �����
����� $n$, � � �������� $X$ ����ͣ� ��������� ���� ���� $x$, ���
������� $\KS(y|x)<n/2$. ����� ������ ����� �� ���������� ��
����������� $n/2$. �������, ��� ����� �� ������ $n-O(\log n)$. �
����� ����, ����� $p$ --- ��������� ���������, ������� ���� $y$
�� ����� ����� $x$, ��� �������� $\KS(y|x)<n/2$. ����� �����
������ ���� ����� ��������� $n/2+O(\log n)$, � ������ � $p$ ��
���������� ��� ��������� $y$, ������� $\KS(y|p)\le n/2 + O(\log n)$. 
������, ���������� ����� $e$ ����� $O(\log n)$, ���
�������� $\KS(y|\langle p,e\rangle)<n/2$. �� �������������
$p(\langle p,e\rangle)=y$ � ������ ��������� $p$ �� ������
$n-O(\log n)$.

\textbf{���������}. ��������� $X$ ����� ������� ��������,
�������������, ������, ������� ����� �� ����� $2n$.

\medskip

\subsection*{��������� ������ $(a\to b)\to b$}

����������� ������ ����������, ��� ����������� � �������������
��������� ����� ������ ����������. � ��������� ������� ��� ��
���, �� �������������� �� ���������� ������� ��������������
������.

�����~$a,b$ --- �������� �����. ��������� $(a\to b)$ ���
��������� ���� ��������, ������� �� ����� $a$ ���� $b$.
��������~\cite{sv}, ���
      $$
\KS((a\to b)\to b)=\min\{\KS(a),\KS(b)\}+O(\log N)
      $$
��� ����� ���� $a,b$ ����� �� ����� $N$. �����������, ��� ���
����������� ����� �������, ������� ����������� ��������� ��
�������������.

\begin{thm}
        \label{basic}
��� ����� ���� $a$ � $b$ ����� �� ������ $N$
���ģ��� ��������� $f$, ����������� $a$ � $b$,
��� �������
        $$
\KS(b|f)=\min\{\KS(a),\KS(b)\} + O(\log N).
        $$
\end{thm}

\begin{proof}
        %
� ���� ������� ($\le$) ����������� �������� ��� ����� ���������
$f$, ����������� $a$ � $b$. � ����� ����, ���� ����� ��������� �
����� �� ���� $a$ � $b$, ����� ������������ $b$.

�������, ��� ��� ��������� ������� $f$ ����� � ��������
�����������. ����� $m$\� ������������ �� ���������� $\KS(b|f)$
��� ���� �������, ����������� $a$ � $b$. (��� ���� ��
�������������� ��������� ���������, ������̣����� �� ���������
���� ���� ����� �� ����� $N$ �� ���������� � ��� �� ���������,
��� ��� ��� �������� ��������� ��������� � �������� ���������
����������� ������������. ������� �����, ��� � ���������������
��������� ��� ������� ����� ��������� � �� �����������.)
��� ���� ��������, ��� ��������� ����
�� ������ �� ���� $a$ � $b$ �� ����������� $m+O(\log N)$.

���������� ��������� $S$ ��� $\langle a',b'\rangle$ ���� �����
�� ������ $N$, ��� ������� ��������� ����� ��������:
\emph{$\KS(b'|f)\le m$ ��� ������ ������� $f$, ������̣���� ��
���� ������ ����� �� ����� $N$ � ����������� �������� � ��� ��
���������, ��� ������� $f(a')=b'$}. �� ���������� ���� $\langle
a,b\rangle$ ������ � $S$.

��������� $S$ ����� �����������, ���� $N$ � $m$. � ���� �����
������������ ����� ��������� ����, � ������� �������� ���
�������� ����������� �� � ������ ��� (����� ���������������); ��
$S$ ��������� ��������� ������������ $\tilde S$, �������
�������� �������� ���������� ������� ������������ ������������.
���� $\langle a,b\rangle$ ��� �� ������� ������������ $\tilde
S$, �� � $\tilde S$ ���� ���� ���� � ��������� $a$, ���� ���� �
��������� $b$ (����� �� �� �� ��������� $\langle a,b\rangle$).

������� ���������� ��������, ��� $\tilde S$ �������� �� �����
$O(2^m)$ ��������� (����� ���������� ����� ��������� ���� �
������������ ��������� $\tilde S$ �������� $m$ ����� � ���������
������������ ����~$a$, ����~$b$).

� ����� ����, ��������� $\tilde S$ ����� ��������� �� �������
��������� ������� $g$. ���� $\langle a',b'\rangle\in \tilde S$,
�� $g(a')=b'$ � ������ $\KS(b'|g)\le m$ �� ���������� ($\tilde
S$ �������� ������������� $S$). ������, � $\tilde S$ ������� ��
����� $O(2^m)$ ��������� $b'$, � �� ���������� �� ������� ��,
������� ��� � $\tilde S$.
        %
\end{proof}

\subsection*{����������������� �������������}

����������� ����������� ������ ����� ��������� �������������. ��
����� �������� ���������� � �����~$b$ ���������� ��������, ���
�������� �����~$a$, ������ ��� ��������� ��������� $f$. (������
�~$a$ ��� ��������� �������� ����� ������������ �����~$b$.) ���
���� �� �����, ����� ��� �������ݣ����, �� ���� �����, ��
������� �����~$a$, ��������� $f$ ����� ���������� ���������
���������� �~$b$, �� ���� ����� ��������� $\KS(b|f)$ ����
����������� ���������. ��� �� ��� ������, ��� ��������� �� �����
���� ������ $\KS(b)$ � �� ����� ���� ������ $\KS(a)$ (���������
������ �~$a$ ���������~$f$ ��������� ����� ������������~$b$).
�������~\ref{basic} ����������, ��� ��� �������
($\min\{\KS(a),\KS(b)\}$) ������������� �����������.

����� ����������� ���������������� ������� ���� ������, �����
�������ݣ���� ����� ��������� ������ ����� $c$. ���� �����������
(�������������� ����������������) ��������� ����� ������� $f$,
����������� $a$ � $b$, ��� �������
        $$
\KS(b|f,c) = \min\{\KS(a|c),\KS(b|c)\};
        $$
��� ������� �������� ���������� ��������� ���������� � $b$ (�
����� ������ ������� $c$). ��������� ������, ����� ���������
����������� (� ��� �������������� ��������� ��������������
�������~\ref{basic}):

\begin{thm}
        \label{relativized}
����� $a,b,c$~--- ����� ����� �� ����� $N$. ����� ���ģ��� �����
$f$, ��� ��������:

\textup{(1)}~$\KS(b|a,f)=O(\log N)$;

\textup{(2)}~$\KS(b|c,f)=\min\{\KS(a|c),\KS(b|c)\}+O(\log N)$.
        %
\end{thm}

�������~(1) �������, ��� ���������~$f$ ��� �����ݣ���� (�������
�����~$a$) �������� ��� ����������� ���������� �~$b$, �
�������~(2) �������, ��� ��� �������ݣ���� (������� ������~$c$)
��� �������� ���������� ��������� ���������� �~$b$.

\textbf{���������}. � ������� ������� ����� ����������, ��� ���
�������������� �������~\ref{basic} ���������� � �������� $f$
����� ���������� �������� $b$ ��� ��������� $a$ --- �������,
����� � Σ� �� ����� \�� ������ ����������\��. �� ��� �� ���:
���� $a$ � $b$\� ����������� ��������� ����� �����~$n$, ��~$b$
�������� ����� ���������� ���������, �� �� ������� �
��������~$f$ (��������� $\KS(b)$ � $\KS(a)$ ������ �~$n$, �
$\KS(b|b)$ ������ � ����). � ���� ������� ����� ����� �
��������~$f$ ��������� ����� $a\oplus b$ ����~$a$ �~$b$ ��
������ $2$ --- ��� ��������� �������� $a$ ������������~$b$, ��
$\KS(b|f)\approx n$.

���������������� �������� � ������� ��������
��������~\cite{muchnik-codes}, ����� ����������� ��������
�������� ����������� �������~\ref{basic}. �������� ������� �
������� �������� ��������, ���������� ����� $b'$, �������
�������� ����������� ��������� $b$ ��� ��������� $a$, �������
������������ $b$. ��� ��������, ��� $\KS(b'|b)=O(\log N)$,
$\KS(b|a,b')=O(\log N)$ � ����� $b'$ ����� $\KS(b|a)+O(\log N)$.
���������� ����� ����� $a'$, ������� �������� �����������
��������� $a$ ��� ��������� $b$, ������� ������������~$a$, �
�������� ��� �� ����� � $b'$ (������� ������ ���� ��� �������
����, � ����������� �� ����, � ������ �� ���� $a$ � $b$ ������
���������), ��������� $a''$. ������ ����� ����� � ��������~$f$
����� $a''\oplus b'$.

���� $f$ � $a$, �� ����� �������� $a'$ � ����� $a''$ ���
�������������� ���������� (������, � ���������������
�������������� �����������), ����� ���� ����� �������� $b'$ �
����� $b$. �������� ��������� �����, ���
$\KS(b|f)=\min\{\KS(a),\KS(b)\}$ � ��������������� ���������.

� ����� ����, � ��������������� ���������
        \begin{multline*}
\KS(b|f)=\KS(b,f|f)=\KS(b,b',f|f)=\KS(b,a''|f)\ge \\ \ge
\KS(b,a'')-\KS(f)\ge'KS(b,a'')-|f|=\KS(b,a'')-\KS(b|a)
        \end{multline*}
����� $a'$ � $b$ ���������� (����� ��������������� ��������
����������), ������� ����� $a''$ (������� ���������� �� $a'$ �
��������������� ����������) ����� ���������� � $b$. �������
������ ������ ����� ���������� ��� $\KS(b)-\KS(b|a)+\KS(a'')$,
��� ����� $\min\{\KS(a),\KS(b)\}$. (����� ���������������
�������������� �������~\ref{basic}).

������������ ����� ����������� � ���, ��� ����� $f$ ����������
�������������� (�� $N$) ����� � ���� ���������� ��������� �����
$\KS(b|a)$. (� ������ �������������� ����� $f$ ���� �������� �
��������������� ������� �������� �����������.) ������� �������,
�� �������� ����� �����������:

\begin{thm}\label{th:1bis}
        %
��� ����� ���� ���� $a$ � $b$ ����� �� ����� $N$ ���ģ��� �����
$f$ ����� $\KS(b|a)$, ��� ��������
        $$
\KS(b|f,a)=O(\log N)
        $$
�
        $$
\KS(b|f)=\min\{\KS(a),\KS(b)\}+O(\log N).
        $$
\end{thm}

� ������ �������, ���������� ����� ����������� � ���, ��� ��� ��
���������� (�� ������� ���� ���������������) �� ������
�������������� ���������� $c$ (�� ���� �� ��������� ��������
�������~\ref{relativized}). ����� ����� $a$ � $b$~--- ���������
����������� ����� ���������� ����� $2n$, � $a_1$, $a_2$ [$b_1$,
$b_2$]~--- ������ � ������ �������� �����~$a$ [��������������
$b$]. ����� ����� $c$ ������� �� ���� ������� $a_1\oplus
a_2\oplus b_1$ � $a_2\oplus b_1\oplus b_2$. �����
$\KS(a|c)=\KS(a,c|c)=\KS(a,b|c)=2n$, $\KS(b|c)=2n$, ��
$\KS(b|c,a\oplus b)=0$.

� ��������� ������� �� ����� ������������� ��������������
������������� ��������� ��������� $f$, ������� �������� ���
���������� � $b$ ��� ������� $a$, �� �� ��� ������� ������ $c$.

\section[������������� ���������� �������� ����������� ���������]
{������������� ���������� ��������\\ ����������� ���������}

������ �� �������, ��� ���� ����� $a$ �������� ���������� �����
���������� (������ ������, ����
$\KS(a|c)\ge\KS(b|c)+\KS(b|a)+O(\log N)$), �� ����������
��������� $f$, ������� �������� ���������� �
�������~\ref{relativized} ���������� � ����� ���������
$\KS(b|a)+O(\log N)$. ��� ����� �� ���������� ���������
������������� �����.

\subsection*{������������� �����}

\textbf{�����}. \textit{��� ����� ����������� $m$ � $n\ge m$
���������� ��������� $\mathcal{F}$ ������� ����
$\mathbb{B}^n\to\mathbb{B}^m$, ��������� �� $2^m\poly(n)$
        % [����� $5n2^m$]
������� �
���������� ����� ���������: ��� ������ ����� $b\in\mathbb{B}^m$
� ��� ������ ������������ $\mathcal{F}'$, ����������� �� �����
�������� ���� ������� �� $\mathcal{F}$, ��������� ����� ��
������ ����������� $b$, �� �������� ��������� ������� ��
$\mathcal{F}'$, �������� �� ����� $O(2^m)$
        % [����� $5\cdot2^m$]
 �����.}

��������� �������� ��������� $\mathcal{F}$, � ������� �ģ� ����
� �����, ����� �������� ���:
        $$
\forall b\,\forall \mathcal{F}'\subset\mathcal{F}
\bigl[ |\mathcal{F}'|\ge \frac{1}{2}|\mathcal{F}| \ \Rightarrow \
|\{a\in\mathbb{B}^n\mid f(a)\ne b \text{ ��� ���� $f\in\mathcal{F}'$}\}|=O(2^m)
\bigr]
        $$
(������� �����, ��� ������� $n\ge m$ �������: ��� $n<m$
����������� ����� ��������� ��������� �������, ���������
���������� ���� $a$ ���� $O(2^m)$.)

���� ���������� �����: �������, �� ������� ���������� � $b$,
���������� � ����� ������� ��������� �����������, � ������ �����
��� ���ģ��� �������, ����������� $a$ � $b$, ���� ������ $a$ ��
����������� ������ ��������� ���������� (��� ����� �������������
������������� ��~$a$, ��� ��� ��� ���������� ����� �����
���������).

\begin{figure}[h]
\begin{center}
   \includegraphics[scale=1]{muchnik-cryptography-shen.mps}
\end{center}
\caption{����� ������� (��~$50\%$) �� $\mathcal{F}$ ���������;
��� �� ����� ������� ���������� ��������� ����� �����������,
�� ������ $O(2^m)$ �����.}
\end{figure}

\begin{proof}
        %
��������� ������������� �����, ����ͣ� ��������� ��������� ��
$2^t$ ��������� ������� $\varphi_1,\ldots,\varphi_{2^t}$. (���
��� ������� ���������� � ���������� ������������ � ���������
���� ������� $\mathbb{B}^n\to\mathbb{B}^m$; ������ ��������
���������~$t$ �� ������� �����.) ������ ����������� ����, ���
���� ����� �� �������� ��������� ���������. ��� ��������, ���
��������
        \begin{itemize}
\item $b\in\mathbb{B}^m$;
\item ��������� $S\subset\mathbb{B}^n$ ��
$s\cdot 2^m$ ��������� (���������~$s$ �� ������� �����);
\item  ��������� $I\subset\{1,2,\ldots,2^t\}$, ���������� �������� ����
��������,
        \end{itemize}
��� �������
        $$
\varphi_i(a)\ne b \text{ ��� ������ $a\in S$ � ��� ������ $i\in I$} \eqno(*)
        $$
������ ����������� ����� �������. ���������� ��������� $b$ ����
$2^m$, ���������� ��������� $I$ �� ����������� $2^{2^t}$, �
���������� ��������� $S$ �� ����������� $(2^n)^{s2^m}$. ���
������������� $b$, $S$ � $I$ ����������� ���������� �������
$(*)$ ����
        $$
\left( 1 - \frac{1}{2^m}\right)^{2^{t-1}\cdot s2^m}
        $$
(������ �� $2^{t-1}$ ������� � ������� � $I$ � ������ �����
$a\in S$ �� �������� �~$b$ � ������������~$(1-1/2^m)$). �����
��� ����������� �������� ������� ������
        $$
2^m\cdot 2^{2^t} \cdot 2^{ns2^m} \cdot
\left( 1 - \frac{1}{2^m}\right)^{2^{t-1}\cdot s2^m},
        $$
� ���� ��������, ��� ��� ��������� ��������� ���������
���������� ��� ��������� ������ �������.
��������, ��� $(1-1/2^m)^{2^m}\approx 1/e$ (� ������� �������
���������, ��� ����� ���), ����� ���������� ��� ���
        $$
2^{m+2^t} \cdot 2^{ns2^m} \cdot
(1/e)^{s2^{t-1}}.
        $$
�������� ���� ������ �����, ������� �������� $2^t$ � $2^m$ �
���������� ������� (��������� $2^t,2^m\gg m,n,s$). ��� �����,
����� ����� ��������� ����������� ��������� ��� ���������.
�����أ� ��������� ����������� �� ��� ����� $(1/e)^{s2^t/4}$,
� ������� ��� ����� � ������ � ������ ������������. ��� �����, �����
        $$
2^{m+2^t} \cdot
(1/e)^{s2^{t}/4} < 1
        $$
�
        $$
2^{ns2^m} \cdot
(1/e)^{s2^{t}/4}<1.
        $$
������ ����������� ����� ���������, ���� ����� ���������~$s$
���������� �������. ���������� ������� �����������
(� ������� ������� ����� ���������
��~$s$) ����� ��������, ������� $2^t=2^m\poly(n)$.
         %
\end{proof}

\subsection*{�������� ���������}

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

\begin{thm}\label{thm:main}
        %
���ģ��� ����� ��������� $C$, ��� ��� ����� ���� $a,b,c$ �����
�� ����� $N$, ��� �������
        $$
\KS(a|c) \ge \KS(b|c) + \KS(b|a) + C\log N,
        $$
���������� ����� $f$ ����� �� ����� $\KS(b|a)+C\log N$,
��� ��������
$\KS(b|a,f)\le C\log N$ �
$\KS(b|c,f)\ge \KS(b|c)-C\log N$.
        %
\end{thm}

������� ������� ��������, ��� ��������� � ������������
���������� ����� $a$ �������� ���������� ����������,
������������� � \�� ����������\��\ (�������� ����� $c$);
���������� �������, ��� ����� $f$ ��������� ������������ $b$ ��
$a$ � ����� (����� ����� ����) ���������� ��������� �����, �
����� �� �������� �������������� $b$ �� $c$. (�� ���� ����������
$O(\log N)$ ������������ ���� � �� �� ���������~$C$, ��
��������� � ������ $C$ ����������� ���������� ������, ��� ��
�������������.)

\begin{proof}
        %
�������� ������� �� �������� �����������~\cite{muchnik-codes} �
���ģ� ����� $b'$ ����� $\KS(b|a)$, ��� �������� ���������
$\KS(b|b',a)$ � $\KS(b'|b)$ ����� $O(\log N)$. ��������
������������� ����� � �������� ��������� �����������
$\mathbb{B}^n\to\mathbb{B}^m$ � ���������� � ��� ����������,
���� $m$ ������ ����� $b'$, �� ���� $\KS(b|a)$, � $n$ ������
����� $a$. ��� ����������� �������� ����� �������, ��� ���������
$\mathcal{F}$ �������� �������, �� ���� ������� ���������
$O(\log N)$, ��������� ��� ������ $m$ � $n$ ��������� ������� �
������� ���������� ����� ������ ���������.

����������� ������� � ���� ��������� (��� � � ����� ������
������� ���������) �� ������ �������� ������� $b$ ��� ���������
$c$ (����� ����� �������� �������� $\KS(b|c)-\KS(b|c,f)$). �
����� ����, � ��������� $O(\log N)$ ��� ����� ���������� ���
$\KS(f|c)-\KS(f|b,c)$ (�� ������� � ��������� ���� � ��������
���������), ������� �������� ����� ������ ���� �������� �����
��������� ��������� (� ������ ������ $m+O(\log N)$), �������
������� �������� �������� ���� $O(\log N)$ � ��������
��������������� ������������ ����ۣ��.

������� � ��������� $\mathcal{F}'$ ������ ������� �� �����
�����������, �� (�� �����) ������� �� ��������� ���� ����
$\langle a',b'\rangle$ ��� ���� $a'$ ����� $n$, ����� $O(2^m)$
\�� ������\��\ $a'$, � ��� ���� ���������, ��� $a$ �� ������ �
����� ������. ��� ����� ���������� ��������, ���
        $$
\KS(a'|c) < \KS(b|c)+\KS(b|a)+O(\log N)
        $$
��� ���� ������ $a'$. � ����� ����, ���� $b$ � $c$, � �����
$\KS(b|c)$ (��������� ����� �������� $O(\log N)$ �����, � �
��������������� ��������� �� ����� ����������), �����
����������� ��� ������� $f$, �� �������� � ���������
$\mathcal{F}'$ (���������� ������� $b$ ��� ��������� $c$), �
������ � �����, �� �������� ��������� ������� �� ���������
$\mathcal{F}'$. (��������, ��� $b'$ ����� ����� ������������ ��
$b$ � ��������������� ����������.) ���� ����� �� ����� �� �����
$O(2^m)$, ������� �� ��������� ��� ��������� $b,c$ �� �����
$m+O(\log N)$. ��������
        $$
\KS(a'|b,c)\le \KS(b|a)+O(\log N)
        $$
��� ���� ������ $a'$, � ������
        $$
\KS(a'|c) \le \KS(a'|b,c)+ \KS(b|c)+O(\log N)\le \KS(b|a)+\KS(b|c)+O(\log N),
        $$
��� � �����������.
        %
\end{proof}


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

������� �� ���������
� �������~\ref{thm:main} ����� ���������� �������������.
������, ���� ����� $a,b,c$ ������� ����������, �� �������,
����� ��������� ����� $a$ ���� ����� ������ ���������
�����~$b$, � ��� �������� ������� (������ ����� ������
���������� ����� ����� ������ ����������, ��� �� ����� ��������?
����� ����, ������� $\KS(a)>\KS(b)$ ���� �� ����������?).

� ���� ������� �� �������, ��� ����������� � �������
�������~\ref{thm:main} �� ����� ���� �����������: ���� ����� ��
���������, �� ����� ���������, ��� ��� ����� $f$, ��� �������
��������� ����������� �������~\ref{relativized}, ����� �����
������� �����. ������ ����������� (��. ����
�������~\ref{thm:negative}) � ��� �������������� ��������
�������, � �� ���Σ� � ����� �������� �����������, �������,
������, ���� ������ � ����� ������� ���������� �����~$c$. �����
�� �������, ��� ����� ��������� ��������� �����~$c$.

����� ������� ��� ����� $a,b,c$, ���������� ������ ����������:
����� �� ����� ������� (������, �������������� �� ����������
���� ��� ���� �������������������) ��������� $f$, ���������� $b$
��~$a$, ����������� �������� ��������� $b$ �� $c$. � ����
������� ����� $a$ � $b$ ����� ����� ��������� �������� $1{,}3n$
� $n$ ��������������, � �� �������� ���������� ����� ������ �
����. (����������� $1{,}3$ ������ ���������� �����������; �����,
��� �� ������ $1$ � ������~$2$.) C�������� $b$ ��� ��������� $c$
����� ����� �������� $n$, ��� ��� ���������� $c$ � ��������
������� �� ��������� ��������� $b$. � ��� ���������� (�
�������~$c$) ����� ��������� $f$, ���������� $b$ �� $a$,
����������� ��������� �������� ��������� $b$: ������
$\KS(b|c)\approx n$ ���������� $\KS(b|f,c)\approx 0{,}3n$.

�������� ���� ����������� ������: ����� $c$ ���� ����� ��������,
����������� $a$ � $b$ (�� ��� ���� ��� $a$ ����� $c$ �� ��������
������� ���������� � $b$). ����� ��� ���� ��������� ���������
$f$, ������� ����� ��������� $a$ � $b$. ��� ��� �������� ������
$b$ ��� ���������~$c$? �� �����, ��� � $c$, � $f$ ��������� $a$
� $b$, ������� $a$ �������� ����� �� ������� ���������
$c(x)=f(x)$. ��� ������� ����� �����������, ���� $c$ � $f$
(��������� $f$ ����� ���� ���������� �� �����, �� ��� ��
������). ���� ������� ����, �� ����� ������ $a$ (� ��� �����
�~$b$), ������ ��� ���������� ����� � ������������ �����
�������. ����� ���������� ��� ��������� $c$ � $f$, � �����
��������� ������ �����, ��� $\KS(b)$ (������� ����� $\KS(b|c)$;
��� �� ��������, ���� �� ���� $c$ �� �������� ���������� ��
$b$).

�������, ��� � ������� ������������ ����� ������ ���������, ����
�������� ������� ���� ���� $\langle a,b\rangle$ ��������������� ����
($1{,}3n$ � $n$), � � �������� $c$ ������� ��������� ������� (�
����������� � ���������� ��������������� ����), ������ �������
�������� ����� $\langle a,b\rangle$. (�� �� ����� ������������� ������������,
���������, ���� ������� ������� ��������� �������, � ����� �� ţ
������� ������� ��������� �����.)

����� $a$ � $b$ ����� ����� ������ ��������� � ����� ��������
���������� � ������� ������������. ���� ������� ������, ���
��������� $b$ ��� ��������� $c$ ����� ������ � $n$. � �����
����, �������� ������� $c$ � ����������� ����� $1{,}3n$ �
���������� ����� $n$ ��������� ����������� ����� ��������
�������� ���������� ����� ��� (����� $2^{0{,}3n}$), 
� ������ ������������� ������������ ��� ������
���������� ��������� ����� ţ ������� ������ � ������������, �
������� ����� �������� ����� �������� ���� ��� ��������� �������
$c$.

����� ������ ���� ��������� ��������� $f$, ����������� $a$ �
$b$, ���ޣ� ��� ����� �� ����� ������� ����� (�����������
�������, ��� ��, ��� ���� �������~\ref{relativized}). �������
������� ����� ����� ��������� $f(x)=c(x)$? � �������� ��������
(��� ������ $f$ � ��������� $c$) ����� ������� ����� �����
$2^{0,3n}$ (� ������ ����� ���������� � ������������ $2^{-n}$, �
����� $2^{1{,}3n}$); ����� �� ������������, ��� $f$ �����
����������, �� ���� ���, ������� ����� ������ ������.
����������� ������� ����� ���������� ��� ������ ������� $f$ �
�������� ��������� $c$ ����� ������������, ������� �������, ���
���������������� ������� � ������� �������� ����� ����� �����
�����������. ��������� ����� ����� �� ����� �����, �� � ��
����������� ����� ����� ����� �����������, � � �������
������������ ��������� ������� $c$ �� ����ģ� �� � ���� �� ����
�����. ��� ������, ��� ��� ����� ������� ��������� $c(x)=f(x)$
��� ����� �� ����� ������� ��������� $f$ ����� ����� ����
������� ����� $2^{0{,}3n}$ �������, � ������ ���������
$\KS(a|f,c)$ � $\KS(b|f,c)$ ����� ���� ���� ������ $0{,}3n$, ���
�� � �������.

�� �� �������� ��������� ��������������� ������, ��� ��� �����
�������� ����� ������� (� �������) �����������. � ������, ��
����� ����� ����� $c$ ������������ ��������� ��������� (� ��
���������������� ���������, ��� � ���������� �����������);
��������� ����� $c$ ����� �������� �� $\KS(b)$ ������, ���
��������� �������� $f$, ��� ������� ��� ����� �������������.
(��� �� �����������: ��� ������ �������� $f$ �� ������
``������������'', ��� ������� ������� � ������ $c$ ���������.)

���� �����������\� ����� ����� �� ������� ��������� �������
$c$\� �����������, ������ ������ $c$ ����� ���������� 
�� ����� ���� ������� (� ����������� � ���������� ������ �����),
� ����� ������� ���������� ��������� $\mathcal{C}$. ��
������������ ������������� ��������, ������� ������
������������� ��� ���������, ������� (������������), ��� �����
��������� ����������, �������� ������, ��� ���������� �������
��������� � ����� ���������� (�������), � ����� �������, ��� ���
����������� ����� $a,b$ ���ģ��� ������� $c$ �� ���������,
������� ������������� ������ �����������. (����� �������, ��
������� �� ������ ������������� ������ $\langle a,b,c\rangle$, � ����� �������
����: ��� ����������� ��� $\langle a,b\rangle$ ���������� $c$.) �����������
������ ���������, �� ��� ����� ������������ ��������� �����~$c$.

������ ��� ������������� ����������� �� ������������ � ���� �����. 
����� ���� ��������� $A$ � $B$. 
����� ��������, ��� ��������� ��������� $\mathcal{F}$ ������� ���� $A\to B$ 
\emph{�������} ������� $c\colon A\to B$, 
���� ��� �����-������ $f\in\mathcal{F}$ ������ ��������� 
$\{a\colon c(a)=f(a)\}$ ������ $4|A|/|B|$ 
(����� ������ ����� ��� � $4$ ���� ����������� ``���������''). 
����� $\mathfrak{H}$~--- ����� �������� ������� �� $A$ � $B$, 
����������������� ���������� $b$ 
(�� ���� $\mathfrak{H}(b)$ ��� ����� $b\in B$ 
�������� ���������� ������� ���� $A\to B$). 
������, ��� ������� $c$ \emph{���������} ���� 
$\langle a,b\rangle\in A\times B$ ��� ������ $\mathcal{F}$ � $\mathfrak{H}$, 
���� $c(a)=b$, ��� ���� $c$ �� ����������� ����������~$\mathcal{F}$ 
� $c\notin \mathfrak{H}(b)$.

\begin{lem}
	%
����� $A$ � $B$~--- �������� ��������� �������� ����, 
���ޣ� $B$ �������� �� ����� ���� ��������� � $|A|\ge 16|B|$. 
����� ����� ���� ����� $\varepsilon\ge 4|B|/|A|$ � $\Phi\le 2^{|A|/4|B|}$. 
����� ���ģ��� ����� ��������� $\mathcal{C}$ ������� ���� $A\to B$ ������� 
\textup(��������\textup)
	$$ 
\max\left\{\frac{20|B|}{\varepsilon},\: \frac{6\Phi\log_2|B|}{\varepsilon},\: 
       6\Phi|B|\log_2|B|\right\},
	$$
��� ��� ������ ��������� $\mathcal{F}$ ������� �� ����� $\Phi$ 
� ��� ������ ������ $\mathfrak{H}$ ��������, 
������ �� ������� ����� ������ �� ����� �������� $|\mathcal{C}|$ 
\textup(�� ���� $|\mathfrak{H}(b)|\le|\mathcal{C}|/4$ ��� ���� $b\in B$\textup) 
�� ����� $\varepsilon$-���� ���� ��� �� $A\times B$ �� ������� �� ����� 
$c\in \mathcal{C}$ ��� ������ $\mathcal{F}$ � $\mathfrak{H}$.
	%
\end{lem}

��������� ����������� ����� �������� ��� 
(�� �������� ������� �� ������� 
$\mathcal{C}$, $\mathcal{F}$ � $\mathfrak{H}(b)$):
        \begin{multline*}
\exists \mathcal{C}
\ \forall \mathcal{F},\mathfrak{H}\\ 
\biggl|\biggl\{\langle a,b\rangle\colon
\forall c\: 
\biggl[ (c(a)=b) \Rightarrow \bigl[(c\in \mathfrak{H}(b))\ \lor\ 
            (\exists f\in \mathcal{F}\:  
                  |\{x:f(x)=c(x)\}|\ge{\textstyle\frac{4|A|}{|B|}}
)\bigr]\biggr]
\biggr\}\biggr|\le\\ \le \varepsilon|A||B|\,.
        \end{multline*}
        
����� ���� ����� (��� ��� �����������) �����. 
��� ����������� �������� ����� ������������, ��� ��������� $\mathcal{C}$ ������� (��� ������, ����� ����� ������ � ��������� ������������ ������� ��������� � ������� ����������). 
����ͣ� � �������� $\mathcal{F}$ ��������� ���� �������, 
������� ������� ��������� (������, �� �����������, ���� ������� ��������), 
� � �������� $\mathfrak{H}(b)$~--- ��������� ���� �������, 
������� ������������ $b$. 
��� ��� $\langle a,b\rangle$, �� �������� � $\varepsilon$-���� ``������'', 
���ģ��� ����������� �� ������� $�$ �� ��������� $\mathcal{C}$.  
��� ������� (������, ţ ������ � $\mathcal{C}$) � ����� ������ ������������� 
(����������� � ����������). 
���� � ���������� � $c$ ��������� �������� ������� ��������� $f$, 
����������� $a$ � $b$, �� ������� $a$ � ��� ����� $b$ ����������: 
���������� ������� ���������� ����� $a$ � ������������ ���� ������� ��������� 
$f(x)=c(x)$. 
��������� ���� $\mathfrak{H}$, � ������ �������, �����������, 
��� $c$ ���� �� ���� ���������� � $b$ 
(����� ������� � ������������ ��������� ���� ��� ��������� $b$). 
��������� �� ������ ��� ��� ������, � ���� ������� �����.

\begin{proof}
	%
� �������� $\mathcal{C}$ ����ͣ� ��������� ��������� ������� ������� �������.
(����� �������, ���  ������� �� $\mathcal{C}$ ���������� ������� 
�� $1$ �� $|\mathcal{C}|$, � ��� ������� ������ $i$ � ������ ����� $a\in A$ 
�� ���������� ���������� �������� $i$-� ������� �� $a$, 
������� ������������� ���� �� ��������� $B$.) 
�������, ��� ����������� ����, ��� $\mathcal{C}$ ``���������'', 
�� ���� �� �������� ��������� ���������, ������~$1$.

������ ����������� ��� ������������� ��������� $\mathcal{F}$. 
��� �����, ����� ��� ������ ������ �������� $\mathfrak{H}$ 
(� ���������� � ����� �������������~--- ��� ��������� �� ����� �������� 
$\mathcal{C}$) ��� ����� ���� ��� $\langle a,b\rangle$ ������� ������� �� 
$\mathcal{C}$, ���������� ����� ����� $\langle a,b\rangle$, 
�� ������������� ���������� $\mathcal{F}$ � �� �������� � $\mathfrak{H}(b)$. 
�������, ��� � ����������� ������������� ������� �� ��������� $\mathcal{C}$: 
���� $\mathcal{F}$, �� ��� �����, ����� ������� ����� �����������. 
�������� ��� ������: ������������� ������� ����� 
(������, ������ �������� ���� ������� �� $\mathcal{C}$) 
� ������������� ������� ���� (������ ��������). 
�� ������ ������ �� ����� ������������ ������������� ������� 
�� ���� ���������� $\mathfrak{H}(b)$, 
� ������ ���� �������� ��������� ��������� 
(�� ������ �������� $|\mathcal{C}|$). 

������� �������, ��� ������� ��������� $\mathcal{F}$ ����������� $\mathcal{C}$ 
����������� ������������ ��������� ���� �������:
	%
\begin{enumerate}
	%
\item $\mathcal{F}$ ������� �� ������ ��������  ������� �� $\mathcal{C}$;
	%
\item ��� ���������� ������ $\mathfrak{H}$, 
� ������� ��� ��������� $\mathfrak{H}(b)$ ����� ������ �� ����� 
\emph{��������} $|\mathcal{C}|$, 
���� ��� �� $A\times B$, 
����� ������� �� �������� �� ���� ������� $c\in \mathcal{C}$, 
�� �������� � $\mathfrak{H}(b)$, ��������� $\varepsilon$.
	%
\end{enumerate}

��� �����, ����� ����� ������������ ���� ���� �������, 
���������� �� ���������� ������������ ��� $\mathcal{F}$, ���� ������ $1$. 
�������, ��� ����������� ������� �� ��� ������ $1/2$, 
��̣���� �� $(|B|^{|A|})^{\Phi}$ 
(��������� ���������~--- ������� ������ �� ���������� ��������� �������� 
$\mathcal{F}$ ������� �� ����� $\Phi$).

������ ������� ������� � ����� ����: 
\emph{���������� ����� ������������ $\mathcal{C}'\subset \mathcal{C}$ 
������� $|\mathcal{C}|/4$,
��� ��� ���� $c\in \mathcal{C}'$ ���ģ��� ����� ������������ $A'\subset A$
������� $4|A|/|B|$ � ����� ������� $f\in \mathcal{F}$, ���
$f(a)=c(a)$ ��� ���� $a\in A'$.}

���������� ��������� $\mathcal{C}'$ ������ ������ ����� ������ ����������� 
� $\mathcal{C}$, �� ���� $2^{|\mathcal{C}|}$. 
��� ������������� ������������ (������, ��� ������� ��������� ��������) 
������� � ����� ��������� ���������� ����������, 
������� ����� ������� ����������� �������������� ������� ��� ����� �� ��� 
� �������� � �������. 
��� ������ ���������� ��������� ����������� $A'$ �������, 
��� ����� ����������� ������� $r$ � ��������� �������~$q$, 
�� ���� $C_q^r$, �� ����������� $q^r/r!\le {q^r}/{((r/3)^r)}=(3q/r)^r$. 
��� $q=|A|$ � $r=4|A|/|B|$ ��������, ���
���������� ���������~$A'$ �� ����������� $(3|B|/4)^{4|A|/|B|}$.

����� �������, ����������� ������� ������� �� ������
$$
   2^{|\mathcal{C}|}\left(
     \Phi
     \left(\frac{3|B|}{4}\right)^{4|A|/|B|}
     \left(\frac{1}{|B|}\right)^{4|A|/|B|}
   \right)^{|\mathcal{C}|/4}=
   \left(2\Phi^{1/4}
     \left(\frac{3}{4}\right)^{|A|/|B|}
   \right)^{|\mathcal{C}|}\,.
$$
                      
����� ��������� �� $|B|^{|A|\Phi}$ 
(����� ��������� �������� $\mathcal{F}$) ��� �������� ������ $1/2$, 
��������� �� ������� ����� $|B|\ge 2$, $|A|\ge 16|B|$, 
$\Phi\le 2^{|A|/4|B|}$ � $|\mathcal{C}|\ge 6\Phi|B|\log_2|B|$.
�������������, �� ���������� ������� �������, ��� 
$|\mathcal{C}|\ge 12$ ��� $\Phi\ge 1$ (������ ������� $\mathcal{F}$ ���������) 
� $|B|\ge 2$, 
������� $1+|\mathcal{C}|\le 13|\mathcal{C}|/12$ � �� $1\le |A|/16|B|$ �������,
��� $1+|\mathcal{C}|\le (13/192)(|A||\mathcal{C}|/|B|)$.
�� $\log_2\Phi\le |A|/4|B|$ �������, ��� 
$(|\mathcal{C}|/4)\log_2\Phi \le (1/16)(|A||\mathcal{C}|/|B|)$.
�������, �� $|\mathcal{C}|\ge 6\Phi|B|\log_2|B|$ �������, ���
$|A|\Phi\log_2|B|\le (1/6)(|A||\mathcal{C}|/|B|)$.
��������� ��� �����������, �������, ��� $19/64 < 1/3 < \log_2 (4/3)$,
� ���������� ��� ����� �� ��������� $2$,
����� ����������� ������������ �������� ��������� �����������.


�����ģ� �� ������� ������� (��������, ��� ������� �� $\mathcal{F}$, 
������� �� ������������ �������������): 
\emph{���������� ����� ����� �������� 
$\mathfrak{H}=\{\mathfrak{H}(b)\}_{b\in B}$, 
� ������� ������ ��������� $\mathfrak{H}(b)$ 
����� ������ �� ����� �������� $|\mathcal{C}|$, 
� ����� ��������� $U\subset A\times B$ ������� $\varepsilon|A||B|$, 
��� ��� ����� ���� $\langle a,b\rangle \in U$ 
� ��� ����� ������� $c\in \mathcal{C}$, �� ������������� $\mathfrak{H}(b)$, 
�������� $c(a)$ �� ����� $b$.}

����� ��� ����� ������ �������, ��� ��������� $\mathfrak{H}(b)$ 
������� �� �� �������, � �� �� �������� (����� �� $1$ �� $|\mathcal{C}|$). 
(������� ��� ���� ��������� ��� ��.)

����� ������� ����������� ������������� ��� (``�������'') �������, 
����������� $\mathcal{F}$, $\mathfrak{H}$ � $U$. 
����� ��������������� ������� ����� ������� ��� ����������� �� ���� ����� $\langle a,b\rangle$ 
� �� ���� $i\notin \mathfrak{H}(b)$ ������� $c[i](a)\ne b$ 
(``������� ����� $i$ � ����� $a$ �� ����� $b$''). 
������ ���� �� �������, ���� �� ��� ������� ���� ����������: 
����� ���� ���� �� �������� $(1-1/|B|)$ � �������, 
������ ���������� ���� ����� $\langle i,a,b\rangle$, 
�� ���� $\varepsilon|A|\cdot|B|\cdot|\mathcal{C}|/2$. 
(�� �������� ����� ��� $\langle a,b\rangle\in U$ 
�� ���������� ��������� $i$ ��� ������� $b$.) 
��� ������ $a$ (� ����� ��� ������ $i$) ��� ������� ���������� �� ����������, 
�� ������� $c[i](a)\ne b_1$ � $c[i](a)\ne b_2$ ��������. 
��� �������� ��, ��� ����������� ��� ``� ���� ������''~--- ��� ����, 
��� �� �����, ��� $c[i](a)\ne b_1$, ������ ����������� ����������� ������� 
$c[i](a)\ne b_2$ (����������� � $1/|B|$ ����������� �� �������, 
���������� � ��� �������� ���������� �������).  
��������� ������, ����� ������������� ������� � ������ � ���� �� $a$ � $i$ 
� ��������������� ������������ $(1-k/|B|)\le (1-1/|B|)^k$, 
��� $k$~--- ����� ������� � ������.

����� �������, �� �������� ������� ������ ��� ����������� ������� 
(��� ������������� $\mathcal{F}$, $\mathfrak{H}$ � $U$): ��� �� ����������� 
	$$
\left(1-\frac{1}{|B|}\right)^{\varepsilon|A||B||\mathcal{C}|/2}\le
2^{-\varepsilon|A||\mathcal{C}|/2}\,.
	$$
�������� �������� ��� ����������� �� ���������� �������� $U$ 
(�� �� ������ $2^{|A||B|}$), 
�� ���������� ������� $\mathfrak{H}$ (�� �� ������ $(2^{|\mathcal{C}|})^{|B|}$)
� �� ���������� �������� $\mathcal{F}$. 
� ���������� �������
	$$
2^{-\varepsilon|A||\mathcal{C}|/2}
2^{|A||B|}
2^{|\mathcal{C}||B|}
|B|^{|A|\Phi}\,.
	$$
�������� ���������, ��� ��� ������ $1/2$ ��� $|B|\ge 2$,
$\varepsilon\ge 4|B|/|A|$, $|\mathcal{C}|\ge 20|B|/\varepsilon$, 
� $|\mathcal{C}|\ge (6\Phi\log_2|B|)/\varepsilon$.
�������������, $1+|A||B|\le 3|A||B|/2$ ��� �������� $A$ � $|B|\ge 2$,
������� �� $|\mathcal{C}|\ge 20|B|/\varepsilon$ �������, ���
$1+|A||B|\le (3/40)\varepsilon |A||\mathcal{C}|$.
�� $\varepsilon\ge 4|B|/|A|$ �������, ���
$|\mathcal{C}||B|\le (1/4)\varepsilon |A||\mathcal{C}|$.
�������, �� $|\mathcal{C}|\ge (6\Phi\log_2|B|)/\varepsilon$ �������, ���
$|A|\Phi\log_2|B|\le (1/6)\varepsilon |A||\mathcal{C}|$.
��������� ��� �����������, �������, ��� $59/120 < 1/2$,
� ���������� ��� ����� �� ��������� $2$,
����� ����������� ������������ �������� ��������� �����������.
	%
\end{proof}

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

����� $\alpha>0$~--- ��������� ���������. 
����� $m$, $n$, $l$~--- ����������� �����, 
���ޣ� $n\ge 1$, $m\ge n+4$, $m-\alpha\log_2 m\ge n+2$ 
� $l+\log_2 (l+1)\le 2^{m-n-2}$. 
������� $N=\max\{m,l\}$.

\begin{thm}
\label{thm:negative}

����� ���� ����� $a$ ����� $m$ � ����� $b$ ����� $n$,
���ޣ�
	$$
m+n-\KS^{\mathbf{0}'}(a,b)<\alpha\log_2 m.
	$$
����� ���ģ��� ����� $c$ ��������� $n+l+O(\log N)$, ��� ��������
	\begin{itemize}
\item $\KS(c|b)=\KS(c) + O(\log N)$;
\item $\KS(b|a,c)=O(\log N)$;
\item ��� ������ $f$, ��� ������� $\KS(f)\le l-\KS(b|a,f)$, 
      ��������� � $\KS(b|c,f)\le m-n + \KS(b|a,f) +O(\log N)$.
	\end{itemize}
\textup{(}��������� � $O(\cdot)$ ������� �� $\alpha$, ��
�� �� $m$, $n$ � $l$.\textup{)}
\end{thm}

%%\textbf{���������.}
��������, ����� ������� ��� ������� ���������� �������������� ������� 
� �������~\ref{thm:main}. 
�� ��������� $\KS(c|b)=\KS(c) + O(\log N)$ ��������, ���
$b$ � $c$ ���������� � $\KS(b|c)=\KS(b)=n$ (� ��������� $O(\log N)$). 
��������� $\KS(b|a,c)=O(\log N)$, �� � $\KS(a|c)\ge\KS(b|c)-\KS(b|a,c)=n$ 
(� ��������� $O(\log N)$). 
������� �ݣ, ��� $\KS(b|a)= n$ (� ��������� $O(\log m)$). 
����� �������, ���� $\KS(b|a,f) = O(\log N)$ 
��� ���������� ����� $f$ ����� �� ����� $l$, �� 
   $$
\KS(b|c,f) < \min\{\KS(a|c),\KS(b|c)\} + O(\log N)
   $$ 
��� $m - n < n + O(\log N)$, �� ���� ��� $\KS(a) < \KS(b|c) + \KS(b|a)$.

\begin{proof}
����� $A$~--- ��������� ���� ���� ����� $m$, 
$B$~--- ��������� ���� ���� ����� $n$. 
����ͣ� $\varepsilon=1/m^\alpha$ � $\Phi=2^l(l+1)$.
����� ���������, ��� �� ������� �� $n,m,l$ �������, 
��� $A$, $B$, $\varepsilon$ � $\Phi$ ������������� �������� �����.
������� ��������� $\mathcal{C}$ � ���������� � ����� ���������� ����������. 
��� ����� ���������� ����� ���������, ���� $A$, $B$, $\varepsilon$ � $\Phi$, 
� ������� ��������� ������ �������� $\mathcal{C}$ �� ����������� 
��������� ����� ��������� � $\mathcal{C}$ ���� $O(\log N)$, 
�� ���� $n+l+O(\log N)$.

����ͣ� � �������� $\mathfrak{H}(b)$ ��������� 
$\{c\in \mathcal{C}\colon \KS(c|b) \le \log_2|\mathcal{C}|-2\}$. 
����, ��� $|\mathfrak{H}(b)|\le |\mathcal{C}|/4$.

��������� ������� $\mathcal{F}$ �������� ���. 
��� ����� �������� ��  $\Phi$ �������, ��������������� �� $1$ �� $\Phi$. 
�� ����������� ��� ������ $\langle a,b,f\rangle$, 
��� $a\in A$, $b\in B$ � $f$~--- ����� ����� $l$, 
��� �������� $\KS(f) + \KS(b|a,f)\le l$. 
��� ���� ��������� ������ ������� ����� �����, ���������� ������� �����~$l$. 
����� ���������� ����� ������ $\langle a,b,f\rangle$,
�� �������� ������������ � ����� $a$ ��������� $b$ ���� �� �������, 
��� ���������� ������~$f$. 
���� ��� ��� ��� ���������� � ����� $a$ (� �� ����� $b$), 
�� �������� �����, ������� �ݣ �� �������, �������� ��� ������ $f$ 
� �������� ������� � ��������������� ������� ������ $b$ � ����� $a$. 
������ ��� ��������� (����� �� ����������) ����� ���ģ���, 
��������� ��� ������� $f$ ����� �� ����� $2^{l-\KS(f)}$ ������� 
(���� ��� ���������� $f$ ������������� ������, ������, ��� ���������� 
$a$ ��� $2^{l-\KS(f)}$ ������� ���������� � ��������� ������ ��������, 
�� ���� �� ����������� ��� $2^{l-\KS(f)}+1$ ������ $b$, 
��� ������� $\KS(b|a,f)\le l-\KS(f)$~--- ������������), 
� ��� ���� $f$ ����� �� ����� $\sum_{\KS(f)\le l}2^{l-\KS(f)}=
\sum_{k=0}^l\sum_{\KS(f)=k}2^{l-k}=\Phi$ �������.
����� ����, ��� ��� ������ � ��������� ��������� �����������,
���������� ��������̣����� �������� ������� �������������� �����������.

���������� ��������� ��� $\langle a,b\rangle$, 
�� �������� $\mathcal{C}$ ��� ��������� $\mathcal{F}$ � $\mathfrak{H}$. 
�� ���������� �� ����������� $\varepsilon2^{m+n}$. 
� ������ �������, $\mathcal{F}$ � $\mathfrak{H}$ 
����� ���� ���������� ��������� � �������� $\mathbf{0}'$, 
� �� ��� ���������� �������� ��������� ���������� ���, 
������� ��� ����� ���������� ���� 
$\KS^{\mathbf{0}'}(a,b)\le m+n-\alpha\log_2 m$.

����� �������, ��� ����� ���� $a$ � $b$, � ������� 
$m+n-\KS^{\mathbf{0}'}(a,b)<\alpha\log_2 m$, 
���ģ��� ����� $c\in \mathcal{C}$, ��� $c(a)=b$, $c\notin \mathfrak{H}(b)$ 
� ��� ����� $f\in \mathcal{F}$ ���������� ����� $x\in A$, ��� $c(x)=f(x)$, 
�� ������ $2^{m-n+2}$.

�� $c(a)=b$ �������, ��� $\KS(b|a,c)=O(\log N)$.

�� $c\notin \mathfrak{H}(b)$ �������, ��� 
$\KS(c|b) > \log_2|\mathcal{C}|-2$, �� ���� $\KS(c)=\KS(c|b)+O(\log N)$.

�������� ������� $\KS(b|c,f)$ ��� $f$, � ������� $\KS(f)\le l-\KS(b|a,f)$. 
���� ����� $f$, ����� ����������� �� ������� �� $\mathcal{F}$, 
������� �������� $f$. 
���� �� ���, ������, $\tilde{f}$ �������� ���� $\langle a,b\rangle$ 
(����� �������, $\tilde{f}(a)=b$), 
��� ţ ������� ����� �� ����� ${\KS(b|a,f)+O(\log N)}$ �������������� �����. 
������ �� $\tilde{f}$ � $c$ ����� ����������� ��������� ����� $x$, 
��� $c(x)=\tilde{f}(x)$. 
(������ ������, ��� ������ ${\KS(b|a,f)+O(\log N)}$ ����� �� ����� ������ 
������ ����� $\tilde{f}$ � ��������� $\mathcal{F}$, 
� �� ���� �������� �������. 
������ ��� ������������ ������� ��������� $c(x)=\tilde{f}(x)$ 
��� ���������� ����, ��� �� ����� ����������� ���� $\langle x,y\rangle$, 
��� ������� $y=\tilde{f}(x)$, �������� ������� ���������� $\mathcal{F}$.)
��� ��������� �������� $a$ � ������� �������� �� $2^{m-n+2}$ ���������, � �� ����� ������ $a$, �������� �ݣ $m-n+2$ �����. �����, $\KS(b|c,f)\le \KS(a|c,f) + O(\log N)\le \KS(b|a,f) + m - n + O(\log N)$, ��� � �����������.
\end{proof}

\textbf{�������� �������}.

\begin{enumerate}

\item ����� �� � ��������� ������� ������� $c$ ���������
$n+O(\log N)$ ������ ${n+l+O(\log N)}$?\footnote{� ��ϣ� ������� 
��.\,�.\,������ �������, ��� ��� �����, 
�� ������� ����� �������� �������������� �����������
(������� �� ���� ����������).}

\item ��������� ������� ����������, ��� ���� $a$ �� ������� ������� $b$, 
�� ��� ��������� $c$ �������� ��������� ��������� ����������. 
� �� �� ����� �������������� �������������� �������~\ref{basic} 
����������, ��� ��� ������ $c$ �������� ��������� ��������� ������ ��������. 
����� �� ������� �����-�� ������ ���� $c$, 
��� ������� �������� � ��� ������� ���������� �������� ���������?
 
\item ��� ����� ������� � ��������� ���������� 
$\KS(f|b)$, $\KS(f|a,b)$, $\KS(f|a,b,c)$ ��� ��������� $f$?

\end{enumerate}

\begin{thebibliography}{9}

\bibitem{muchnik-codes}
Muchnik~An.~A. Conditional complexity and codes,
     \emph{Theoretical Computer Science},
     v.~271 (2002), issues~1--2, p.~97--109.
[Preliminary version: Andrej Muchnik, Alexej Semenov,
Multi-conditional Descriptions and Codes in Kolmogorov
Complexity, ECCC Technical Report, 2000, no.~15, January~27,
2000.]

\bibitem{sv}
A.~Shen, N.~Vereshchagin.
Logical operations and Kol\-mo\-go\-rov complexity.
\emph{Theoretical Computer Science},
2002, v.~271, pp.~125--129.
\end{thebibliography}

\end{document}
