\documentclass[a4paper,12pt,draft]{article}
\usepackage{amsmath,amssymb,amsthm}

\usepackage[cp1251]{inputenc}
\usepackage[T2A]{fontenc}
\usepackage[russian]{babel}

\newtheorem{thm}{Теорема}
\newtheorem{lemma}{Лемма}
\theoremstyle{remark}\newtheorem{example}{Пример}
\newcommand*{\KS}{KS}
\newcommand*{\KP}{KP}

\begin{document}

Известно~\cite{sv}, что $\KS((a\to b)\to b)=\min\{\KS(a),\KS(b)\}$.
Оказывается, это утверждение можно усилить следующим образом.
\begin{thm}
Для любых слов $a$ и $b$ найдётся такое слово $f$, что
$\KS(b|a,f)=O(1)$ и 
$\KS(b|f)=\min\{\KS(a),\KS(b)\} - O(\log(\KS(a)+\KS(b)))$.
\end{thm}
\begin{proof}
Очевидно, что $\KS(b|f)\le \KS(b)+O(1)$ и 
$\KS(b|f)\le O(\KS(b|a,f))+\KS(a)\le \KS(a)+O(1)$
для любого $f$.

Докажем, что с логарифмической точностью верно и обратное неравенство.
Пусть $A=\{a' : |a'|=|a|\}$, $B=\{b' : |b'|=|b|\}$.
Пусть $m=\max\{\KS(b|f) : f\in B^A\}$.
Рассмотрим множество пар 
$$
S=\{\langle a',b'\rangle\in A\times B : 
\forall f\in B^A (\,f(a')=b' \:\Rightarrow\: \KS(b'|f)\le m\,)\}\,.
$$
Множество $S$ перечислимо (при известных $|a|$, $|b|$, $m$).
Преобразуем его в перечислимое множество пар $\tilde S\subseteq S$
следующим образом: 
вновь встретившаяся в перечислении $S$ пара $\langle a',b'\rangle$
входит в перечисление $\tilde S$, если 
ни $a'$ не встречалось среди первых компонент уже перечисленных пар,
ни $b'$ не встречалось среди вторых компонент.

Множество $|\tilde S|$  содержит не более $2^m$ элементов.
Действительно, 
$|\tilde S|=|\{b' : \exists a'\,\langle a',b'\rangle\in\tilde S\}|$
по построению.
Кроме того, $\tilde S$ можно доопределить до некоторой функции 
$\tilde f\in B^A$. 
Если $\langle a',b'\rangle\in\tilde S$, то $\tilde f(a')=b'$,
откуда по определению $S$ следует, что $\KS(b'|\tilde f)\le m$.
Таким образом, 
$|\tilde S|\le {|\{b':\KS(b'|\tilde f)\le m\}|}\le 2^m$.

Из определения $m$ следует, что 
пара $\langle a,b\rangle$ принадлежит $S$.
Либо $\langle a,b'\rangle$, либо $\langle a',b\rangle$
должно принадлежать $\tilde S$.
Поэтому либо $a$, либо $b$ можно описать при помощи
$\log |\tilde S|+\KP(S)\le m + \KP(|a|)+\KP(|b|)+\KP(m)$ битов.
Взяв в качестве $S$ не множество пар, а множество кратчайших описаний,
можно заменить длины на сложности. 
Можно также убрать $\KP(m)$, поскольку $m\le |b|+O(1)$.
Окончательно получаем, что  
$\min\{\KS(a),\KS(b)\}\le \KS(b|f)+O(\log(\KS(a)+\KS(b)))$
для некоторого $f$, такого что $\KS(b|a,f)=O(1)$.
\end{proof}

Эту теорему можно релятивизовать, 
добавив во второе неравенство условие $c$
(что соответствует формуле 
$\KS((c\land(a\to b))\to b)=\min\{\KS(a|c),\KS(b|c)\}$).

\begin{thm}
Для любых слов $a$, $b$ и $c$ найдётся такое слово $f$, что
$\KS(b|a,f)=O(1)$ и 
$\KS(b|c,f)=\min\{\KS(a|c),\KS(b|c)\} - O(\log(\KS(a)+\KS(b)))$.
\end{thm}

Теоремы утверждают существование $f$.
Возникает естественный вопрос: 
что можно сказать о сложности $f$
и о сложности её построения из $a$ и $b$?
Например, если $a$ и $b$~--- 
случайные независимые слова одинаковой длины,
в первой теореме в качестве $f$ можно взять
$a\oplus b$~--- очевидно, кратчайшее из возможных слов
(но не всякое кратчайшее слово подойдёт: 
$b$~--- контрпример),
которое к тому же легко строится по $a$ и $b$.
Но уже для второй теорему такой пример построить не удаётся.

Релятивизованный вариант теоремы допускает такую 
\glqq криптографическую\grqq{} интерпретацию.
Всеведущий Центр хочет передать Разведчику некоторую информацию $b$.
Разведчик располагает уже некоторой информацией $a$,
которую он может использовать для расшифровки сообщений Центра.
Шпион тоже хотел бы узнать $b$.
Шпион умеет перехватывать сообщения Центра. 
Кроме того, Шпион располагает некоторой информацией $c$.
Задача Центра состоит в том, чтобы передать сообщение Разведчику
так, чтобы Шпион получил как можно меньше новой информации.
Иными словами, сообщение Центра $f$ должно быть
\begin{description}
\item{информативным:} $\KS(b|a,f)=0$,
\item{сохраняющим секретность:} $\KS(b|c,f)$ максимальна.
\end{description}

Очевидно, что $\KS(b|c,f)\le \min\{\KS(a|c),\KS(b|c)\}$
для любого $f$.
Теорема утверждает, что эта верхняя оценка достигается 
при любых $a$, $b$ и $c$.

Следующий естественный вопрос в такой постановке~---
насколько длинным является сообщение, 
в наибольшей степени сохраняющее секретность.
Иными словами, мы рассматриваем теперь такие условия на $f$:
$\KS(b|a,f)=0$, 
$\KS(b|c,f)\le \min\{\KS(a|c),\KS(b|c)\}$
и $\KS(f)$ минимальна.

Очевидно, $\KS(f)\ge \KS(b|a)$.
Оказывается, что эта оценка достигается только при некотором 
дополнительном условии на сложности $a$, $b$ и $c$,
а именно, если $\KS(a|c)\ge 2\KS(b|c)$.
Причём константу $2$ здесь нельзя заменить на меньшую.
Это составляет утверждение следующих двух теорем.


Пусть $a$ и $b$~--- случайные независимые слова одинаковой длины $n$,
$c$~--- пустое слово.
Тогда в качестве $f$ можно взять $a\oplus b$.
(Действительно, зная $a$, по $a\oplus b$ легко восстановить $b$,
а с другой стороны, $\KS(b|a\oplus b)=\KS(a,b|a\oplus b)\ge
\KS(a,b)-|a\oplus b|=n$.)
Сложение но модулю два можно использовать 
и для произвольных $a$ и $b$ (и по-прежнему пустого $c$), если
воспользоваться следующей теоремой Мучника~cite{codes}.

\begin{thm}
Для любых слов $x$ и $y$ найдётся слово $x'$ такое, что
$\KS(x'|x)=O(\log n)$,
$\KS(x|x',y)=O(\log n)$,
$|x'|=\KS(x|y)+O(\log n)$,
где $n=\max\{\KS(x),\KS(y)\}$.
\end{thm} 

Теорема утверждает, что кратчайший код слова $x$ 
при известном слове $y$ можно найти, имея только слово $x$
и небольшую (логарифмическую) информацию о слове $y$.

Пусть $a'$~--- кратчайший код $a$ при известном $b$,
$b'$~--- кратчайший код $b$ при известном $a$.
В слове $a'$ возьмём начало такой же длины, как и $b'$,
а если $a'$ короче~--- дополним его нулями.
Сложим его с $b'$, $f=a'_{1:|b'|}\oplus b'$, это и будет
искомым кратчайшим кодом.
Очевидно, что зная $f$ и $a$ легко восстановить $b$,
и нетрудно показать, что 
$\KS(b|f)=\min\{\KS(a),\KS(b)\}-O(\log n)$.

В присутствии дополнительной информации $c$ такая простая схема
может и не сработать. 
Пусть опять 
$a$ и $b$~--- случайные независимые слова одинаковой длины $n$,
а $a_1$, $a_2$ и $b_1$, $b_2$~---
их первая и вторая половины их.
Пусть $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)=n$,
$\KS(b|c)=n$,
но $\KS(b|c,a\oplus b)=0$.


\begin{thm}
Для любых слов $a$, $b$ и $c$ таких, что
$\KS(a|c)\ge \KS(b|a)+\KS(b|c)$,
найдётся слово $f$ такое, что 
$\KS(b|a,f)=O(\log n)$,
$\KS(b|c,f)=\KS(a|c)-O(\log n)$,
$\KS(f)=\KS(b|a)+O(\log n)$,
где $n=\max\{\KS(a),\KS(b)\}$.
\end{thm}

\begin{proof}
Доказательство теоремы основано на следующей комбинаторной лемме.

\begin{lemma}
Пусть $A$ и $B$~--- конечные множества, содержащие
по крайней мере два элемента.
Пусть $\phi\ge 5|B|\log_2|A|$, $\alpha\ge 5|B|$.

Тогда найдётся $F$~--- множество конечных функций из $A$ в $B$,
которое содержит не более $\phi$ элементов 
и имеет следующее свойство.
Если выбрать любым способом не менее половины функций из $F$,
то для любого $b\in B$ 
существует не более $\alpha$ таких $a\in A$,
что ни для какой функции $f$ из выбранных не верно $f(a)=b$.
\end{lemma}

\begin{proof}
Выберем случайно $\phi$ функций из $A$ в $B$
(равновероятно среди всех таких функций; 
будем считать, что функции могут повторяться.)
Докажем, что с ненулевой вероятностью
это множество функций обладает требуемым свойством.

Вычислим вероятность того, что свойство не выполнено.
Для фиксированных $a$ и $b$ вероятность того, что 
$f(a)\ne b$ для случайной функции $f$,
равна $(1-1/|B|)$.
Для $\phi/2$ независимо выбранных функций\footnote{
Способ выбора, по-видимому, надо рассматривать такой: 
для каждого заранее фиксированного подмножества номеров
от $1$ до $\phi$ мы берём те функции, которые выпали 
при формировании $F$ на шагах с этими номерами.
Опять-таки, в этой ``половине $F$'' функции могут повторяться.} 
вероятность того, что для всех них $f(a)\ne b$,
равна $(1-1/|B|)^{\phi/2}$.
Вероятность того, что это так не для одного фиксированного $a$,
а для $\alpha$ различных элементов из $A$,
равна $(1-1/|B|)^{\alpha\phi/2}$.
Элемент $b$ можно выбрать $|B|$ способами,
$\alpha$ элементов из $A$ можно выбрать не более чем $|A|^\alpha$
способами (для достаточно грубой оценки сверху мы посчитали
число способов выбора с повторением).
Наконец, число способов выбрать $\phi/2$ функций из $\phi$
не больше $2^\phi$ (числа способов выбрать любое подмножество функций).
Таким образом, вероятность того, что случайно выбранные $\phi$
функций не обладают требуемым свойством,
не больше 
$$
 |B|\cdot2^\phi\cdot|A|^\alpha
    \left(1-\frac{1}{|B|}\right)^{\alpha\phi/2}\,.
$$
Пользуясь оценкой $1-1/x\le \mathrm e^{-1/x}$,
получим, что логарифм этой вероятности не превышает
$$
 -\frac{\alpha\phi}{2|B|\ln2}+\phi+\alpha\log|A|+\log|B|\,.
$$
Легко убедиться, что при заданных ограничениях на $\phi$ и $\alpha$
эта величина отрицательна.
\end{proof}

Объясним теперь, как из этой леммы получается доказательство теоремы.
В качестве $A$ возьмём все слова длины не больше $K(a)$,
в качестве $B$~--- все слова длины не больше $K(b|a)+C\log$

\end{proof}

Открытые вопросы.
\begin{enumerate}
\item В первой теореме, когда нет $c$, всегда ли можно выбрать $f$
длины $\KS(b|a)$?
\item Что можно сказать о $\KS(f|b)$? $\KS(f|a,b)$? $\KS(f|a,b,c)$?
\item Четвёртая теорема показывает, что при некоторых условиях
любая кратчайшая $f$ будет несекретной. 
Можно ли отсюда вывести, какова минимальная длина секретной $f$?
\end{enumerate}

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

\bigskip

\begin{verbatim}
Subject: Kolmogorov seminar
Date: Fri Mar  7 10:51:49 MSK 2003

Во втоpник, 11 маpта в 16:20 в аудитоpии 16-10 Главного здания МГУ

на очеpедном заседании Колмогоpовского семинаpа
(pуководители H.К.Веpещагин, А.Л.Семенов, А.Х.Шень)

состоится доклад Ан.А.Мучника и А.Л.Семенова "Кpиптогpафия
с точки зpения теоpии колмогоpовской сложности".

Pассматpивается следующая задача: пpедположим субъекту A известна
инфоpмация (слово) $a$, а субъекту C известно слово $c$. Тpебуется
пеpедать по откpытому каналу связи слово $d$ такое, чтобы A по словам
$a$ и $d$ легко мог восстановить $b$, а субъект $C$ не получал никакой
дополнительной инфоpмации о $b$, т.е. взаимная инфоpмация I(b:d|c)
пpенебpежимо мала.

\end{verbatim}

\begin{verbatim}
Subject: Kolmogorov seminar
Date: Thu Apr  3 17:06:13 MSK 2003

Во втоpник, 8 апpеля Ан.А.Мучник и А.Л.Семенов пpодолжат pассказ
о "Кpиптогpафических задачах с точки зpения теоpии колмогоpовской
сложности".

\end{verbatim}

\emph{У меня в конспекте доклад озаглавлен 
\glqq О секретной оптимальной передаче\grqq.
В первый раз теорема была сформулирована неправильно, 
и ошибка обнаружилась в процессе изложения доказательства.
А.\,Чернов.}

\end{document}