дый ход противника, а противник так много ходов сделать не сможет (см. далее). Таким образом, слово $B$ мы выбрать сможем.

Выбрав $B$, мы начинаем выбирать $A$. Фиксируем допустимую тройку $\langle p, q, r \rangle$ и подсчитаем, сколько слов не годятся из-за неё. Имеется не более $2^r$ слов $B'$ длины $q$, объявленных $r$-простыми относительно $B$. Для каждого $B'$ есть не более $2^p$ слов длины $2n$, объявленных $p$-простыми относительно этого $B'$. Таким образом, нам не годятся $2^{p+r}$ слов (для каждой тройки $\langle p, q, r \rangle$ из множества допустимых троек $M$), всего $2^{p+r} \cdot |M|$. Ещё нам не подходят слова, объявленные плохими (не более $2^{2n-1}$ штук), а также слова, объявленные плохими относительно выбранного $B$ (их не более $2^{n-2}$). Таким образом, искомый ход заведомо возможен, если

$$2^{p+r} \cdot |M| + 2^{2n-1} + 2^{n-2} < 2^{2n}. \quad (*)$$

Теперь надо подсчитать, сколько ходов (в течение одной партии) может сделать противник. Каждый из $|M|$ игроков, отвечающих за допустимые тройки $\langle p, q, r \rangle$, делает не более $2^{2n+r}$ ходов, объявляя слова $r$-простыми, а также не более $2^{q+p}$ ходов, объявляя слова $p$-простыми. Поэтому общее число ходов этих игроков не больше

$$|M| \cdot (2^{\max(2n+r)} + 2^{\max(q+p)})$$

(где максимумы в показателе берутся по всем тройкам из $M$). Сюда ещё надо добавить $2^{2n-1}$ ходов при объявлении слов плохими и $2^{2n} \cdot 2^{n-2} = 2^{3n-2}$ ходов при объявлении слов плохими относительно других слов. Таким образом, обещанное условие на число ходов противника (меньше $2^{3n-1}$) будет выполнено, если

$$|M| \cdot (2^{\max(2n+r)} + 2^{\max(q+p)}) + 2^{2n-1} + 2^{3n-2} < 2^{3n-1}. \quad (**)$$

Учитывая, что $2^k + 2^l$ близко к $2^{\max\{k,l\}}$, легко заметить, что условия (*) и (**)
будут выполнены, если все тройки $\langle p, q, r \rangle \in M$ удовлетворяют неравенствам

$$\begin{align*}
p+r &< 2n-3 \log n - O(1), \\
2n+r &< 3n-3 \log n - O(1), \\
p+q &< 3n-3 \log n - O(1).
\end{align*}$$

(Таких троек не более $O(n^3)$, и мы как раз вычили $3 \log n + O(1)$ как верхнюю оценку для $\log |M|$). Мы не указываем явно константу в $O(1)$ но, скажем, заведомо годится 10. Включим в $M$ все тройки, удовлетворяющие этим неравенствам; в этом случае в описанной игре существует выигрышная стратегия.

Эту стратегию мы будем применять против стратегии противника, которая игнорирует делаемые нами ходы. Она объявляет плохими слова длины $2n$, имеющие сложность менее $2n-1$, объявляет плохими относительно слова $B$ все слова, имеющие условную сложность менее $n-2$, а также объявляет $u$-простыми [относительно простыми] все слова, сложность [соответственно, относительная сложность] которых меньше $u$. (Точнее говоря, этим правилом руководствуется каждый $\langle p, q, r \rangle$-игрок для каждой тройки $\langle p, q, r \rangle \in M$.)

Запустим две описанные нами стратегии играть друг против друга. Это будет алгоритмический процесс, для задания которого достаточно знать число $n$. Момент
его окончания алгоритмически найти нельзя, но он существует, и в этот момент найдётся пара слов $\langle A, B \rangle$, которая обеспечивает наш выигрыш. Покажем, что для них выполнено утверждение теоремы.

Длина слов $A$ и $B$ равна $2n$; сложность равна $2n + O(1)$ (она не может быть меньше, так как иначе эти слова были бы объявлены плохими). Поскольку в нашем процессе мы для каждого $B$ указываем не более $2^n$ различных слов $A$, то $KS(A|B) \le n + O(\log n)$; сложность $KS(A|B)$ не может быть меньше $n - O(1)$, иначе слово $A$ было бы объявлено плохим относительно $B$.

Пусть дано произвольное слово $B'$, для которого $KS(B'|B) < r$ и длина слова $B'$ равна $q$. Можно считать, что $r$ много меньше $n$, скажем, $r < n/2$ (иначе слагаемое $O(r)$ в правой части утверждения теоремы делает его тривиальным). Тогда второе неравенство из трёх выполнено. Поэтому для любого $p$, удовлетворяющего первому и третьему неравенству, сложность $A$ относительно $B'$ больше $p$. Значит для любой пары $\langle p, q \rangle$ из светло-серой области на рис. 12.14, отстоящей от её границы с областью $G$ не менее, чем на $O(r + \log n)$, не существует $B'$ длины $q$ для которого $KS(B'|B) < r$ и $KS(A|B') < p$. Это и требовалось установить.

Теорема 237 доказана. ►

Приведём другое доказательство того же утверждения, использующее вероятностный метод. Оно во многом параллельно игровому<fnref n="1" />, но есть важные различия. Во-первых, вместо того, чтобы реагировать на ходы противника, мы сделаем все ходы сразу же и будем надеяться, что при любых действиях противника мы выиграем. Во-вторых, мы теперь не указываем выигрышные ходы явно, а доказываем, что случайный набор ходов с положительной вероятностью окажется выигрышным.

Техническое замечание: при таком подходе можно без ограничения общности считать, что оба игрока указывают максимальное разрешённое число слов.

Перейдём к формальному изложению, отмечая параллели с игровым доказательством в квадратных скобках. Пусть имеется отображение

$$U: \mathbb{B}^{2n} \times \mathbb{B}^n \to \mathbb{B}^{2n}$$

[значения $U(B, X)$ при данном $B$ и всевозможных $X$ соответствуют $n$-простым относительно $B$ словам в игровом доказательстве]. Пусть фиксировано некоторое конечное множество $M$ троек натуральных чисел и для каждой тройки $\langle p, q, r \rangle \in M$ имеются два отображения

$$V_{p,q,r}: \mathbb{B}^{2n} \times \mathbb{B}^r \to \mathbb{B}^q$$

и

$$W_{p,q,r}: \mathbb{B}^q \times \mathbb{B}^p \to \mathbb{B}^{2n}.$$

Пусть, кроме того, имеется отображение

$$S: \mathbb{B}^{2n-2} \to \mathbb{B}^{2n},$$

а также отображение

$$T: \mathbb{B}^{2n} \times \mathbb{B}^{n-2\log n} \to \mathbb{B}^{2n}.$$

<footnote n="1">¹Читатель мог уже заметить, что многие доказательства в этой книге имеют игровой характер. Более подробно об игровом методе в теории колмогоровской сложности рассказано в обзорах [171, 117].</footnote>
[Отображения $V_{p,q,r}$ и $W_{p,q,r}$ соответствуют ходам $\langle p, q, r \rangle$-игрока в команде противника. Именно, слова $V_{p,q,r}(B, X)$ при всевозможных $X$ суть $r$-простые относительно $B$ слова; слова $W_{p,q,r}(B', X)$ при всевозможных $X$ суть $p$-простые относительно $B'$ слова. Отображения $S$ и $T$ соответствуют ходам двух дополнительных игроков. Именно, $S(X)$ суть плохие слова в количестве не более $2^{2n-2}$ штук, а $T(B, X)$ суть плохие относительно $B$ слова в количестве не более чем $2^{n-2 \log n}$ штук. Границы для числа плохих слов уменьшены по сравнению с игровым доказательством: вместо $2n-1$ взято $2n-2$, а вместо $n-2$ взято $n-2 \log n$. Это будет использовано в оценках.]

Будем говорить, что отображение $U$ покрыто четвёркой $V, W, S, T$ (состоящей из двух семейств отображений и двух отображений), если для всякого слова $B \in \mathbb{B}^{2n}$ и для всякого слова $A$, равного $U(B, X)$ при некотором $X \in \mathbb{B}^n$ [для любого слова $B$ и любого слова $A$, объявленного нами $n$-простым относительно $B$], пара $\langle A, B \rangle$ удовлетворяет одному из четырёх условий:

(1) Слово $B$ входит в область значений отображения $S$ (то есть $B = S(Y)$ при некотором $Y \in \mathbb{B}^{2n-2}$). [Слово $B$ противник объявил плохим.]

(2) Слово $A$ входит в область значений отображения $S$ (то есть $A = S(Y)$ при некотором $Y \in \mathbb{B}^{2n-2}$). [Слово $A$ противник объявил плохим.]

(3) Слово $A$ равно $T(B, Y)$ при некотором $Y \in \mathbb{B}^{n-2 \log n}$. [Слово $A$ противник объявил плохим для данного $B$.]

(4) Найдётся тройка $\langle p, q, r \rangle \in M$ и слово $B'$ длины $q$, для которых

(а) $B' = V_{p,q,r}(B, Y)$ для некоторого $Y \in \mathbb{B}^r$ [$\langle p, q, r \rangle$-игрок команды противника объявил, что слово $B'$ является $r$-простым относительно $B$];

(б) $A = W_{p,q,r}(B', Z)$ для некоторого $Z \in \mathbb{B}^p$ [$\langle p, q, r \rangle$-игрок команды противника объявил, что слово $A$ является $p$-простым относительно $B'$].

Мы докажем (при некотором условиях на множество $M$, указанных далее), что существует отображение $U$, не покрытое ни одной четвёркой $V, W, S, T$. Доказательство вероятностное: мы подсчитаем для данной четвёрки, сколько отображений $U$ ими покрывается (т.е. вероятность для случайного отображения $U$ оказаться покрытым), умножим эту вероятность на число четвёрок и установим, что произведение останется меньше 1.

Подсчёт для одной четвёрки делается так. Пусть фиксированы $V, W, S, T$. Имется не менее $2^{2n-1}$ слов $B$ длины $2n$, нарушающих условие (1). Чтобы $U$ было покрыто, необходимо, чтобы при любом таком $B$ каждое из $2^n$ значений $A = U(B, X)$ для всех $X$ длины $n$ было покрыто одним из условий (2)–(4). Мы убедимся, что для данных $B$ и $X$ вероятность такого события не больше $1/2$. Из независимости следует, что вероятность для случайного $U$ оказаться покрытым не больше

$$ (1/2)^{2^{2n-1} \times 2^n} = (1/2)^{2^{3n-1}}. $$

Для данных $B$ и $X$: не годятся слова $A$, покрытые условием (2) в количестве $2^{2n-2}$ штук, покрытые условием (3) в количестве $2^{n-2 \log n}$ штук, а также покрытые условием (4) слова $W_{p,q,r}(V_{p,q,r}(B, Y), Z)$ в количестве $2^r \times 2^p$ штук для каждой тройки $\langle p, q, r \rangle \in M$. Всего получается не больше

$$ 2^{2n-2} + 2^{n-2 \log n} + 2^{r+p} \cdot |M|, $$
что не больше $2^{2n-1}$ (половины всех слов), если

$$r + p + \log |M| < 2n - 3 \quad (*)$$

при всех $\langle p, q, r \rangle \in M$ (это и будет первое из списка требований к $M$).

Осталось оценить количество всех четвёрок $V, W, S, T$. Для $V_{p,q,r}$ (при данных $p, q, r$) имеется не более

$$(2^q)^{2n \times 2^r} = 2^{q \cdot 2^{2n+r}}$$

вариантов, для $W_{p,q,r}$ (при данных $p, q, r$) имеется не более

$$(2^{2n})^{2^q \times 2^p} = 2^{2n \cdot 2^{q+p}}$$

вариантов, для $S$ имеется не более

$$(2^{2n})^{2^{n-2}} = 2^{2n \cdot 2^{2n-2}}$$

вариантов, для $T$ имеется не более

$$(2^{2n})^{2n \times 2^{n-2 \log n}} = 2^{(2^{3n}/n)+1}$$

вариантов. Первые две оценки возводим в степень $|M|$ и получаем оценку на число вариантов для $V$ и $W$ в целом, после чего полученные оценки перемножаем и заключаем, что общее количество четвёрок $V, W, S, T$ не превосходит

$$2^q \cdot 2^{2n+r} \times |M| \cdot 2^{2n \cdot 2^{q+p}} \times |M| \cdot 2^{2n \cdot 2^{2n-2}} \cdot 2^{(2^{3n}/n)+1},$$

а двоичный логарифм этого числа не превосходит

$$q \cdot 2^{2n+r} \times |M| + 2n \cdot 2^{q+p} \times |M| + 2n \cdot 2^{2n-2} + (2^{3n}/n) + 1,$$

что будет меньше $2^{3n}$ (как требуется для завершения доказательства), если

$$2n + r + \log q + \log |M| < 3n - O(1) \quad (**)$$

и

$$q + p + \log n + \log |M| < 3n - O(1). \quad (***)$$

(Мы пользуемся тем, что $2^a + 2^b$ отличается не более чем в константу раз от $2^{\max(a,b)}$; два других условия в логарифмической шкале имеют вид $2n - 2 + \log 2n < 3n - O(1)$ и $\log(2^{3n}/n + 1) < 3n - O(1)$, и выполнены автоматически.)

Все три условия $(*)$ – $(***)$ будут заведомо выполнены, если

$$p + r < 2n - 3 \log n - O(1),$$

$$2n + r < 3n - 4 \log n - O(1),$$

$$p + q < 3n - 4 \log n - O(1)$$

для всех $\langle p, q, r \rangle$ из $M$, поскольку в таком случае $|M| = O(n^3)$.

Поэтому, взяв в качестве $M$ множество троек, удовлетворяющих трём указан- ным только что неравенствам, мы заключаем, что существует отображение $U$, не покрытое никакой четвёркой $V, W, S, T$ (при этом $M$).
При известном $n$ такое отображение $U$ можно найти перебором, поэтому (важный момент!) первое отображение $U$ с такими свойствами будет иметь сложность не больше $\log n$.

Возьмём это $U$ и конкретную четвёрку $V, W, S, T$, которой оно (по доказанному) не покрыто. А именно, пусть $\{S(\cdot)\}$ (множество значений отображения $S$) — все слова длины $2n$, имеющие сложность менее $2n-2$. Пусть при любом $B \in \mathbb{B}^{2n}$ множество $\{T(B, \cdot)\}$ составляют все слова, имеющие условную сложность (отноственно $B$) менее $2\log n$. Пусть при данных $p, q, r$ среди $V_{p,q,r}(B, \cdot)$ встречаются все слова условной сложности (относительно $B$) менее $r$, а среди $W_{p,q,r}(B', \cdot)$ встречаются все слова условной сложности (относительно $B'$) менее $p$.

Раз $U$ не покрыто, найдётся пара слов $A$ и $B$, не обладающая ни одним из свойств (1)-(4). Отсюда следует, что $KS(A) = 2n + O(1)$ (слово имеет длину $2n$ и не может иметь сильно меньшую сложность, иначе его покрывает $S$). Аналогично $KS(B) = 2n + O(1)$. Условная сложность $KS(A|B)$ равна $n + O(\log n)$: она не может быть больше, так как $A = U(B, X)$ для некоторого слова $X$ длины $n$, а сложность $U$ есть $O(\log n)$; она не может быть меньше, так как иначе было бы выполнено свойство (3). Наконец, ни при каких $p, q$ и $r$ не найдётся слова $B'$ длины $q$, при котором $KS(B'|B) < r$ и $KS(A|B') < p$, иначе было бы выполнено свойство (4).

Далее рассуждаем как раньше (в игровом доказательстве); на этом вероятностное доказательство теоремы 237 заканчивается.

Наконец, можно привести и «геометрическую» конструкцию, доказывающую то же самое утверждение. (В отличие от задачи выделения общей информации, здесь геометрическое рассуждение даёт примерно те же оценки сложности.)

А именно, возьмём поле из $2^n$ элементов (или примерно такого количества, если мы хотим ограничиться вычетами по простому модулю) и рассмотрим двумерную плоскость над этим полем. Пусть $\langle A, B \rangle$ — случайная пара, состоящая из точки этой плоскости и проходящей через неё прямой. Тогда сложности как раз такие, как требуется в теореме 237.

Далее, пусть имеется слово $B'$, для которого

$$KS(B'|B) \le r, \quad KS(B') \le q, \quad KS(A|B') \le p. \quad (*)$$

Мы хотим показать, что пара $(p, q)$ находится в $O(r) + O(\log n)$ окрестности множества $G$, установив, что в противном случае пара $(A, B)$ имела бы меньшую сложность. В самом деле, оценим количество пар $(A, B)$, для которых выполняются условия (*) при некотором $B'$. Каждое из $2^q$ слов $B'$ задаёт два множества:

* те слова $A$ (длины $2n$), при которых $KS(A|B') \le p$ (обозначим это множество $U_{B'}$);

* те слова $B$ (длины $2n$), при которых $KS(B'|B) \le r$ (обозначим его $V_{B'}$).

Множество $U_{B'}$ содержит $2^p$ элементов (точнее, $O(2^p)$, но для простоты записи мы ограниченные множители опускаем). Множество $V_{B'}$ может иметь разный размер (это зависит от $B'$), но известно, что эти множества покрывают множество из $2^{2n}$ слов длины $2n$ не более чем в $2^r$ слоёв (для каждого $B$ есть не более $2^r$ слов $B'$, простых относительно него).
Нам надо доказать, что объединение всех $U_{B'} \times V_{B'}$ покрывает лишь небольшую часть всех пар (так что случайная пара в него не попадёт). Для оценки количества покрытых пар применим уже известное свойство графа инцидентности (две пря- мые не могут проходить через две точки) и вытекающую из него оценку (лемма о четырёхугольниках, с. 398).

Нам будет удобно использовать утверждение этой леммы в такой форме (равно- сильной, как легко проверить): если в прямоугольной таблице $l \times L$ представлены звёздочки, и никакие четыре не стоят на пересечении двух строк и двух столбцов, то число звёздочек не превосходит

* $O(L)$ при $l \le \sqrt{L}$;

* $O(l\sqrt{L})$ при $l \ge \sqrt{L}$.

При этом следует отдельно рассматривать случай «больших» и «малых» $V_{B'}$. Начнём с первого. Если $V_{B'}$ содержит больше $\sqrt{|U_{B'}|}$, то есть больше $2^{p/2}$ элементов, то число покрытых пар не больше $2^{p/2}|V_{B'}|$ элементов для данного $B'$. Сумма по всех $B'$ не больше $O(2^{p/2}2^2n2^r)$ (множество размера $2^{2n}$ покрыто не более чем в $2^r$ слоёв).

Теперь перейдём к малым $V_{B'}$. Для них $U_{B'} \times V_{B'}$ покрывает не более $O(2^p)$ элементов, и всего для $2^q$ различных $B'$ получается $O(2^{p+q})$.

Таким образом, если $p+q < 3n - O(\log n)$ и $(p/2) + 2n + r < 3n - O(\log n)$, то случайная пара $(A, B)$ не будет обслужена ни одним из слов $B'$. (Тут ещё на- до заметить, что множество обслуженных пар можно перечислять, зная $n, p, q, r$, то есть $O(\log n)$ битов информации.) Второе неравенство можно переписать как $p + 2r < 2n$; хотя это и немного хуже, чем неравенство $p + r < 2n$, которое бы- ло в первом доказательстве, но всё равно мы остаёмся в пределах оценки $O(r)$, упомянутой в теореме.

Третье доказательство теоремы 237 закончено.

**Замечание.** Это третье доказательство позволяет получить простое множество пар, большинство пар в котором удовлетворяют теореме (другими словами, по- зволяют получить стохастическую в смысле раздела 14.2 пару, удовлетворяющую условиям теоремы).

Того же самого, хотя и не в столь наглядной форме, можно добиться и моди- фикацией второго (вероятностного) доказательства. Мы считали отображение $U$ покрытым, если для всех пар определённого вида нечто верно; ослабим это условие и будем говорить, что $U$ покрыто, если для половины пар нечто верно.

Для доказательства существования непокрытого $U$ можно воспользоваться сле- дующей (тривиальной) оценкой. Если вероятность каждого из независимых $2^k$ со- бытий не больше $1/16$, то вероятность того, что произойдёт не менее $2^{k-1}$ собы- тий, не больше $2^k \cdot (1/16)^{2^k/2} = 2^{-k}$. Поэтому нужно заменить вероятность $1/2$ на $1/16$, а всё остальное как раньше.

(Можно и иначе: не рассматривать множеств $S$ и $T$ и параллельно все до- пустимые тройки, а доказывать, что с близкой к единице вероятностью для слу- чайно выбранного $U$ для пар, для которых выполнено условие (4), мала. Эти малые доли и малые отклонения от единицы затем складываются для всех троек из $M$.)
# 13. Информация и логика

## 13.1. Задачи, логические операции, сложность

Под задачей будем понимать произвольное множество двоичных слов, а под решением задачи — любой его элемент. Смысл этого определения можно пояснить следующим образом. Решение любой точно поставленной задачи можно записать в подходящем формальном языке. Можно считать, что решение задачи закодировано при помощи некоторого двоичного слова. Мы будем интересоваться лишь количеством информации в решениях задачи, а не содержательной её стороной, поэтому задачу естественно отождествлять с множеством её решений.

Определим сложность задачи X как наименьшую сложность её решений:

$$KS(X) = \min\{KS(x) \mid x \in X\}.$$

При этом минимум пустого множества (задачи, не имеющей решений) полагаем равным $+\infty$.

Например, сложность синглетона $\{x\}$ совпадает со сложностью самого x. Другой пример: в разделе 1.2 мы сталкивались с задачей описания натурального числа, не меньшего заданного числа $n$. Её сложность обозначалась через $KS_{\ge}(n)$. Используя новую терминологию, можно сказать, что $KS_{\ge}(n)$ есть сложность задачи, множество решений которой состоит из всех чисел, больших или равных $n$.

Если есть две задачи X и Y, то можно рассмотреть задачу «решить обе задачи X и Y», а также задачу «решить хотя бы одну из задач X и Y (указав при этом, какая именно из двух задач решена)». Другими словами, решениями задачи «X и Y» можно считать пары, первая компонента которых есть решение задачи X, а вторая — задачи Y. А решениями задачи «X или Y» можно считать решения любой из задач с дополнительным указанием, какая именно из двух задач решена. Таким образом, мы приходим к таким определениям логических операций над задачами:

$$X \wedge Y = \{[x, y] \mid x \in X, y \in Y\}, \\ X \vee Y = \{[0, x] \mid x \in X\} \cup \{[1, y] \mid y \in Y\}.$$

Здесь $[x, y]$ обозначает код пары слов $\langle x, y \rangle$ при некотором вычислимом однозначном кодировании пар слов.

Сложность задачи $\{x\} \wedge \{y\}$ равна сложности пары $\langle x, y \rangle$, а сложность задачи $\{x\} \vee \{y\}$ равна минимуму из сложностей х и у (с точностью до константы). И вообще, для любых задач X, Y сложность задачи $X \vee Y$ равна наименьшей из сложностей задач X и Y (с $O(1)$-точностью).
Задача X ∧ Y называется **конъюнкцией** задач X и Y, а задача X ∨ Y — дизь-юнкцией задач X и Y. Есть альтернативное естественное определение дизьюнкции задач, отражающее следующую идею. Можно предложить решающему написать два слова, из которых первое должно быть решением первой задачи или второе — решением второй задачи, при этом решающий может и не указывать, какой из двух случаев имеет место (что-то похожее происходит на письменных экзаменах по математике, когда требуется решить хотя бы одну задачу из двух, студент записывает два решения двух задач, и одно из них оказывается правильным, но студент не обязан указывать, какое). Этой идее соответствует такое формальное определение «псевдодизьюнкции» задач:

$$
X \tilde{\lor} Y = \{[x, y] \mid x \in X \text{ или } y \in Y\}.
$$

Сложность псевдодизьюнкции отличается от сложности дизьюнкции всего лишь на
O(1), однако это принципиально разные задачи, о чём мы поговорим позже.

332 Докажите, что KS(X ˜ Y) = KS(X ∨ Y) + O(1).

Другой (промежуточный) вариант «псевдодизьюнкции» получится, если просто
объединить множества решений задач X и Y. (Студент пишет только одно решение,
но не указывает номер задачи, к которой оно относится.)

Условную сложность KS(y|x) тоже можно понимать как сложность некоторой алгоритмической задачи, а именно задачи преобразования х в у. Эта задача получается из задач {x} и {у} помощью операции над задачами, называемой им-пликацией. А именно, решениями задачи X → Y будут программы, которые дают некоторое решение задачи Y в применении к любому решению задачи X. Точнее говоря, зафиксируем некоторый язык программирования, в котором программами являются двоичные слова, и будем обозначать [p](x) результат применения программы p к слову х. Если вычисление не заканчивается, то [p](x) не определено. Язык программирования должен быть универсальным, то есть иметь программы для всех вычислимых функций. Более того, мы предполагаем, что он допускает эффективную трансляцию с любого другого языка программирования (задаваемая им универсальная функция должна быть гёделевой, или главной, см. [175]).

Итак, положим

$$
X \to Y = \{p \mid \forall x (x \in X \Rightarrow [p](x) \text{ определено и } [p](x) \in Y)\}.
$$

Например, в разделе 6.4 мы изучали величину KS(x |≥ n), которая определялась
как наименьшая сложность программы, которая выдает x, получив на вход любое
натуральное число, не меньше n. Используя новые обозначения, можно написать
KS(x |≥ n) = KS({m ∈ N | m ≥ n} → {x}). Другой пример, с которого мы нача-
ли: сложность задачи {x} → {y} равна условной сложности у при известном x (с
точностью до константы).

Некоторые теоремы из главы 12 естественным образом могут быть сформули-
рованы как утверждения о сложности тех или иных задач.

А именно, решениями задачи (x → у) ∧ (y → x) (мы опускаем скобки при записи синглетонов) являются пары программ, из которых первая преобразует х в у, а
вторая — у в х. Мы рассматривали задачу о минимальной возможной сложности такой пары и установили, что она равна максимальной из условных сложностей $KS(y|x)$ и $KS(x|y)$ (с точностью до $O(\log KS(x, y))$).

Другой пример. Решениями задачи $(x \to z) \land (y \to z)$ являются пары программ, из которых первая преобразует $x$ в $z$, а вторая — у в $z$. Мы доказали, что минимально возможная сложность такой пары примерно равна максимуму условных сложностей $KS(z|x)$ и $KS(z|y)$ (с точностью до $O(\log KS(x, y))$).

**333** Найдите сложность задачи $a \to (b \to c)$. [Указание. Эта задача эквивалентна $(a \land b) \to c$.]

**334** Найдите сложность задачи $a \land (b \to c)$ (с логарифмической точностью). [Ответ: $KS(a) + KS(c|a, b)$. Указание: имея программу для $a$ и программу получения $c$ из $a$ и $b$, можно указать и программу получения $c$ из $b$. Неравенство в другую сторону: прибавив к предлагаемому ответу $KS(b|a)$, мы получим $KS(a, b, c)$, поэтому достаточно доказать, что по $a$, программе переделки $a$ в $b$ и программе переделки $b$ в $c$ можно восстановить тройку $(a, b, c)$.]

**335** Докажите, что сложность задачи $(x \lor y) \to (x \lor \tilde{y} y)$ ограничена константой, однако сложность обратной задачи $(x \lor \tilde{y} y) \to (x \lor y)$ такая же, как и у задачи $x \lor y$ с точностью до $O(\log n)$, где $n$ — наибольшая из длин $x, y$. [Указание. Пусть $p$ — любое решение задачи $(x \lor \tilde{y} y) \to (x \lor y)$. Будем говорить, что пара слов $(u, v)$ длины не больше $n$ согласована с $p$, если для всех слов $w$ длины не больше $n$ программа $p$ в применении к обоим словам $[u, w]$, $[w, v]$ дает некоторое решение задачи $u \lor v$. Тогда для любой согласованной с $p$ пары $u = x$ или $v = y$.]

**336** Докажите, что сложность задачи

$$((x \lor \tilde{y} y) \to (x \lor y y)) \to (x \lor \tilde{y} y)$$

есть $O(\log n)$, где $n$ — наибольшая из длин $x, y$.

Две последних задачи объясняют разницу между обычной дизьюнкцией и псевдодизьюнкцией. В частности, из них следует, что задачи $x \lor \tilde{x}$ и $x \lor \tilde{y}$ существенно различны, хотя они и имеют почти одинаковые сложности. А сложность задачи $(x \lor \tilde{x} x) \to x$ оказывается примерно равной сложности самого $x$.

## 13.2. Сложность задач и интуиционистская логика

Импликация обладает следующим свойством: если задачи $X$ и $X \to Y$ просты, то и задача $Y$ проста:

$$KS(Y) \le KS(X) + KS(X \to Y).$$

Это неравенство выполняется с точностью $O(\log KS(X))$, а также с точностью $O(\log KS(X \to Y))$. Оно является обобщением неравенства

$$KS(y) \le KS(x) + KS(y|x),$$
верного для любых слов x, y (также с логарифмической точностью). Как и неравенство для слов, оно может быть усилено:

$$KS(X \wedge Y) \leq KS(X) + KS(X \rightarrow Y).$$

Однако обратное неравенство уже неверно (в отличие от аналогичного неравенства для слов).

**337** Приведите пример множеств X, Y, для которых $KS(X \wedge Y)$ значительно меньше, чем $KS(X) + KS(X \rightarrow Y)$. [Указание. В качестве X можно взять множество всех случайных слов длины $n$, а в качестве Y — множество всех случайных слов длины $2n$.]**

Операции $\wedge$, $\vee$, $\rightarrow$ как операции над задачами восходят к определениям Колмогорова [61] и Клини [60], введённым для интерпретации интуиционистского исчисления высказываний (IPC); сложность задачи в описанном выше смысле рассматривалась в [157]. Читателя, желающего больше узнать о логических исчислениях, в том числе об IPC, мы отсылаем к книге [174]. А здесь мы обсудим связь между выводимостью формулы в интуиционистском исчислении высказываний и максимальной возможной сложностью порождённой ею задачи.

Пусть $\Phi(p, q, ...)$ — пропозициональная формула со связками $\wedge, \vee, \rightarrow$. Для любых множеств слов X, Y, ... рассмотрим задачу $\Phi(X, Y, ...)$, которая получится, если подставить в формулу $\Phi$ вместо переменных эти множества.

Сейчас будет вполне уместным следующее замечание. В нашем определении операций над задачами имеется произвол: в выборе спаривающей функции $x, y \rightarrow [x, y]$, в выборе языка программирования и, наконец, в выборе слов 0, 1 при определении дизьюнкции. Однако сложности любой задачи, посчитанные при двух различных выборах, отличаются не более чем на константу. Точнее надо сказать так. Пусть $\Phi(p, q, ...)$ — пропозициональная формула, а $X, Y, ...$ — произвольные множества. Пусть $\Phi'(X, Y, ...)$ и $\Phi''(X, Y, ...)$ — две задачи, которые получились, если использовать разные спаривающие функции $[x, y]', [x, y]''$, разные языки программирования $U'(p, x) = [p]'(x)$ и $U''(p, x) = [p]''(x)$, и, наконец, разные пары слов $a', b'$ и $a'', b''$ в определении дизьюнкции. Тогда разность сложностей задач $\Phi'(X, Y, ...)$ и $\Phi''(X, Y, ...)$ ограничена константой по абсолютной величине. Доказать это можно по индукции. Точнее, по индукции для любой формулы можно построить две вычислимых функции: $f_{12}^{\Phi}$ преобразует любое решение задачи $\Phi'(X, Y, ...)$ в некоторое решение задачи $\Phi''(X, Y, ...)$, а $f_{21}^{\Phi}$ — любое решение задачи $\Phi''(X, Y, ...)$ в некоторое решение задачи $\Phi'(X, Y, ...)$.

Для пропозициональных переменных обе функции — это тождественная функция. Если формула $\Phi$ является конъюнкцией формул $\Psi$ и $\Theta$, для которых обе функции уже определены, то $f_{12}^{\Phi}$ действует так: данное слово $s$ представляем в виде $[u, v]',$ затем применяем к $u$ и к $v$ функции $f_{12}^{\Psi}$ и $f_{12}^{\Theta}$, соответственно; полученные результаты спариваем с помощью второй спаривающей функции. Функция $f_{21}^{\Phi}$ действует аналогично. Аналогично рассматривается случай дизьюнкции.

Наконец, если формула $\Phi$ есть $\Psi \rightarrow \Theta$, то функция $f_{12}^{\Phi}$ определяется следующим образом. Рассмотрим вычислимую функцию $V(s, b) = f_{12}^{\Theta}([s]'(f_{21}^{\Psi}(b)))$. Если $s$ — решение задачи $\Psi'(X, Y, ...)$ — $\Theta'(X, Y, ...)$, а $b$ — решение задачи $\Psi''(X, Y, ...)$,
то $V(s, b)$ будет решением задачи $\Theta''(X, Y, \dots)$. Будем рассматривать $V$ как язык программирования; мы предполагали, что возможна эффективная трансляция этого языка в язык $U''$ (формально говоря, мы используем, что $U''$ — главная универсальная функция). Поэтому существует всюду определённая вычислимая функция $t: \Xi \to \Xi$, для которой $[t(s)]''(b) = V(s, b)$. Функция $t$ и будет искомой функцией $f_{12}^\Phi$ для формулы $\Phi$.

**338** Проведите это рассуждение подробно.

Связь введённых понятий с интуиционистским исчислением обнаруживается в следующем факте: если формула $\Phi(p, q, \dots)$ выводима в интуиционистском исчислении высказываний, то сложность задачи $\Phi(X, Y, \dots)$ ограничивает строку $s$, которая является решением задачи $\Phi(X, Y, \dots)$ для всех множеств $X, Y, \dots$. Это доказывается индукцией по длине вывода в IPC. Например, для формулы $p \to (q \to p)$ (одна из аксиом IPC) эта строка есть следующая программа: «преобразовать данное нам $x$ в программу, которая печатает $x$ на любом входе».

**339** Завершите это рассуждение и докажите, что для каждой выводимой в IPC формулы $\Phi(p, q, \dots)$ существует строка $s$, которая является решением задачи $\Phi(X, Y, \dots)$ для всех множеств $X, Y, \dots$.

Верно и обратное: если формула $\Phi(p, q, \dots)$ без отрицаний не выводится в IPC, то сложность задачи $\Phi(X, Y, \dots)$ не ограничена константой. Более того, справедлива следующая теорема о полноте для формул без отрицаний:

**Теорема 238.** Пусть пропозициональная формула $\Phi(t_1, \dots, t_k)$ со связками $\wedge, \vee, \to$ (без отрицаний) невыводима в IPC. Тогда найдётся положительное $\varepsilon$ и последовательность непустых конечных множеств $X_1^n, \dots, X_k^n$ (для $n = 1, 2, \dots$), состоящих из слов длины не более $n$, для которой сложность задачи $\Phi(X_1^n, \dots, X_k^n)$ не меньше $\varepsilon n$ при всех достаточно больших $n$.

Это — главное утверждение настоящей главы. Мы его докажем, приняв на веру некоторое чисто логическое утверждение о невыводимых в IPC формулах. В этом доказательстве важную роль играют оценки сложности задач, которые возникают при подстановке одноэлементных множеств в (невыводимые в IPC) пропозиционные формулы. Некоторые из таких задач интересны сами по себе (см. уже приведённые примеры). Сейчас мы займемся анализом сложности некоторых других формул, представляющих интерес с логической точки зрения.

### 13.3. Примеры

Начнём с формулы<fnref n="1" />

$$((p \to q) \to p) \to p.$$

Эта формула, называемая законом Пирса (Peirce's Law), является тавтологией (истинна при любых булевых значениях переменных), но невыводима в интуиционистском исчислении высказываний. При этом сложность задачи $((x \to y) \to x) \to x$

<footnote n="1">¹Примеры этого раздела взяты из работы [157]</footnote>
(как обычно, мы опускаем скобки при записи синглетонов) есть $O(\log n)$ для любых слов $x, y$ длины не более $n$ (теорема 239 ниже). С другой стороны, как мы уже говорили, взяв интиуиционистски невыводимую формулу и подставляя вместо переменных подходящие конечные непустые множества слов длины не более $n$, можно получить задачу сложности не меньше $\varepsilon n$. В частности, это верно и для закона Пирса. Тут нет противоречия: сложность задачи ($(X \to Y) \to X) \to X$ мала по сравнению со сложностями $X, Y$, если $X, Y$ — синглетоны, но может быть сравнимой со сложностями $X, Y$, если $X, Y$ — непустые конечные множества.

**Теорема 239.** Сложность задачи ($(x \to y) \to x) \to x$ есть $O(\log n)$ для любых слов $x, y$ длины не более $n$.

◀ Нам достаточно указать алгоритм, который по $n$ и любому решению задачи $(x \to y) \to x$ находит $x$. Этот алгоритм работает так. Пусть $p$ — решение задачи $(x \to y) \to x$. Пусть $S$ есть обозначает множество всех слов длины не больше $n$. Для любой всюду определённой функции $\tau: S \to S$ (их конечное число) зафиксируем некоторую программу $l_\tau$, вычисляющую эту функцию. Назовем пару $(u, v) \in S \times S$ согласованной с $p$, если $[p](l_\tau) = u$ для всех $\tau: S \to S$ с $\tau(u) = v$. Исходная пара $(x, y)$ согласована с $p$. Имея $p$ и $n$, мы начинаем перечислять согласованные с $p$ пары и выдаем первую компоненту $u$ первой попавшейся пары $(u, v)$. Докажем, что в самом деле $u = x$. Действительно, в противном случае существует функция $\tau$, для которой $\tau(x) = y$ и $\tau(u) = v$, и программа $p$ на входе $l_\tau$ выдаёт одновременно два различных слова $u$ и $x$. ▶

С формальной точки зрения в предыдущем доказательстве есть небольшой пробел. А именно, мы неявно использовали, что имеется алгоритм который находит программу $l_\tau$, имея функцию $\tau$ (заданную списком своих значений). Это следует из предположений о нашем языке программирования (список значений тоже можно рассматривать как программу для функции в некотором другом языке программирования, и этот второй язык можно эффективно транслировать в наш по предположению). Заметим ещё, что в наших рассуждениях можно было рассматривать не все функции, а только функции некоторого класса: важно лишь, что для любых двух пар (аргумент, значение) с различными аргументами найдётся функция из класса, через них проходящая. Например, годятся линейные функции $ax + b$ над конечным полем.

**340** Докажите, что в условии предыдущей теоремы можно заменить $O(\log n)$ на $O(\log k)$, где $k$ — максимальная из сложностей $x, y$. [Указание. Надо перейти от слов $x, y$ к их программам длины не более $k$ относительно оптимального декомпрессора. В доказательстве следует заменить $S$ на множество всех слов длины не больше $k$, а программа $l_\tau$ должна работать так: на входе $u$ она находит первое описание слова $u$ длины не более $k$, применяет к нему $\tau$ и применяет оптимальный декомпрессор к получившемуся слову.]

Из доказанного утверждения и неравенства

$$KS(Y) \le KS(X) + KS(X \to Y) + O(\log KS(X))$$

следует, что $KS(x) \le KS((x \to y) \to x) + O(\log n)$ (где $n$ — наибольшая из длин $x, y$). Но это не единственный способ доказывать неравенства подобного вида: суще-
ствуют такие формулы $A(p, q)$ и $B(p, q)$, что для любых слов х, у сложность задачи $B(x, y)$ не превосходит сложности задачи $A(x, y)$, однако сложность импликации $A(x, y) \rightarrow B(x, y)$ велика по сравнению со сложностями х, у (при некоторых х, у). Вот пример таких формул: $(x \rightarrow y) \rightarrow y$ и $x \lor y$. (Эти формулы, кстати, эквиваленты в классической логике.) Их сложности отличаются всего лишь на $O(\log n)$, что мы сейчас докажем, однако сложность импликации $((x \rightarrow y) \rightarrow y) \rightarrow (x \lor y)$, как мы увидим, может быть примерно равна $n$.

Начнем с вычисления сложности задачи $(x \rightarrow y) \rightarrow y$.

**Теорема 240.** Сложность задачи $(x \rightarrow y) \rightarrow y$ равна сложности задачи $x \lor y$ (с точностью $O(\log n)$, где $n$ — наибольшая из длин х, у).

Эта сложность, как мы знаем, равна минимуму сложностей слов х и у с точностью $O(1)$.

◀ Нам достаточно предъявить алгоритм, который по любому решению задачи $x \lor y$ даёт некоторое решение задачи $(x \rightarrow y) \rightarrow y$, и другой алгоритм, который по любому решению задачи $(x \rightarrow y) \rightarrow y$ и логарифмическому от $n$ количеству дополнительной информации даёт некоторое решение задачи $x \lor y$.

Первый алгоритм, получив на вход $[0, x]$ или $[1, y]$, должен найти некоторую программу, которая преобразует любое решение задачи $(x \rightarrow y)$ в $y$. Если нами получено слово $[1, y]$, то мы выдаём такую программу: не читая входа, печатать $y$. Если же нам дано слово $[0, x]$, то мы выдаём следующую программу: применяем данное нам решение задачи $(x \rightarrow y)$ к $x$, получая тем самым $y$, и печатаем его.

Теперь предъявим алгоритм, который по любому решению задачи $(x \rightarrow y) \rightarrow y$, числу $n$ и ещё одному дополнительному биту информации находит некоторое решение задачи $x \lor y$.

Пусть $p$ — любое решение задачи $(x \rightarrow y) \rightarrow y$. Обозначим через $S$ множество всех слов длины не более $n$. Для любой функции $\tau$: $S \rightarrow S$ можно алгоритмически найти программу $l_\tau$, вычисляющую эту функцию. На этот раз назовём пару $(u, v) \in S \times S$ согласованной с $p$, если $[p](l_\tau) = v$ для всех $\tau$ таких, что $\tau(u) = v$.

По определению пара $(x, y)$ согласована с $p$. Могут существовать и другие пары, согласованные с $p$. Однако у любых двух согласованных с $p$ пар $(u', v')$ и $(u'', v'')$ совпадают первые или вторые компоненты. Действительно, если первые компоненты различны, то существует функция $\tau$, отображающая $u'$ в $v'$, а $u''$ в $v''$. Применение $p$ к $l_\tau$ должно давать одновременно и $v'$, и $v''$. Поэтому вторые компоненты должны совпадать, если не совпадают первые.

Множество согласованных с $p$ пар можно перечислять, зная $p$ и $n$. Запустим процесс его перечисления. Пусть $(u, v)$ — первая появившаяся пара. Мы знаем, что либо $u = x$, либо $v = y$, но не знаем, какой из двух случаем имеет место. Именно здесь нам нужен дополнительный бит информации: получив его, мы выдаём $x$ или $y$ (в зависимости от значения этого бита).

Это рассуждение можно обобщить и получить такой результат:

**Теорема 241.** Сложность задачи $(x \rightarrow y) \rightarrow z$ (с точностью $O(\log n)$, где $n$ — наибольшая из длин $x$ и $y$) совпадает со сложностью задачи $z \lor (x \land (y \rightarrow z))$.

Из утверждения задачи 334 следует, что сложность последней задачи равна минимуму из $KS(z)$ и $KS(x) + KS(z | x, y)$.
◀ Нам достаточно предъявить алгоритм, который по любому решению второй задачи даёт решение первой задачи, и другой алгоритм, который по любому решению первой задачи и логарифмическому от $n$ количеству дополнительной информации даёт решение второй задачи.

Сначала предъявим первый алгоритм. По определению решением исходной задачи является любая программа, которая преобразует любое решение задачи ($x \to y$) в $z$. Решения же второй задачи — это слово $z$, а также пары, состоящие из $x$ и программы, переводящей $y$ в $z$. Если данное нам решение второй задачи есть слово $z$, то мы выдаём следующее решение исходной задачи: не считая данной нам программы, печатать $z$. Если же данное нам решение второй задачи есть слово $x$ и программа, преобразующая $y$ в $z$, то мы выдаём следующее решение исходной задачи: применяем данное нам решение задачи ($x \to y$) к $x$, получая тем самым $y$. Затем применяем программу, переводящую $y$ в $z$, к найденному $y$.

Теперь предъявим алгоритм, который по любому решению исходной задачи, числу $n$ и ещё одному дополнительному биту информации находит некоторое решение второй задачи.

Пусть $p$ — любое решение задачи ($x \to y \to z$). Обозначим через $S$ множество всех слов длины не более $n$. Для любой функции $\tau: S \to S$ зафиксируем некоторую программу $l_\tau$, вычисляющую эту функцию. Назовем тройку $(u, v, w) \in S \times S \times S$ согласованной с $p$, если $[p](l_\tau) = w$ для всех $\tau \subset S$ ($u = v$).

Покажем, что либо у всех согласованных троек одинаковы первые компоненты, либо одинаковы третьи компоненты. Предположим, что есть две согласованные тройки с различными третьими компонентами: $(u, v, w)$ и $(u', v', w')$, причём $w \neq w'$. Заметим, что тогда $u = u'$, иначе функция, которая переводит $u$ в $v$ и $u'$ в $v'$, должна одновременно переводиться в $w$ и $w'$, что невозможно. Теперь можно заметить, что и у всех остальных согласованных троек (если они есть) первая компонента та же, иначе эту тройку можно было бы совместить с любой из двух имеющихся и получить два разных значения третьей компоненты — противоречие.

По определению тройка $(x, y, z)$ согласована с $p$. Множество согласованных с $p$ троек можно перечислять, зная $p$ и $n$. Запустим процесс его перечисления. Пусть $(u, v, w)$ — первая появившаяся тройка. Мы уже знаем, что $u = x$ или $w = z$.

Первый случай: $w = z$. В этом случае мы (если нам скажут дополнительно, что этот случай имеет место) знаем $z$.

Второй случай: $u = x$. Тогда мы можем найти $x$, и остаётся решить задачу $y \to z$. Но эта задача проще, чем задача ($x \to y \to z$), поскольку из у можно получить решение задачи $x \to y$.

Итак, имеем решение задачи ($x \to y \to z$, число $n$ и один дополнительный бит, можно найти либо $z$, либо решение задачи $x \land (y \to z)$. (Дополнительный бит нам нужен, чтобы понять, какой из двух случаев имеет место.) ▶

## 13.4. Ещё несколько примеров и доказательство теоремы 238

Теперь мы докажем что сложность задачи ($(x \to y) \to y \to (x \lor y)$ может быть близка к длине слов $x, y$, о чём уже говорилось ранее.
**Теорема 242.** Сложность задачи $((x \to y) \to y) \to (x \lor y)$ для слов х и у длины не более n равна $\min(\text{KS}(x|y), \text{KS}(y|x)) + O(\log n)$. В частности, если х, у — случайные и независимые слова длины n, сложность этой задачи примерно равна n.

◀ Легко убедиться, что сложность задачи $((x \to y) \to y) \to (x \lor y)$ не превосходит $\text{KS}(y|x)$ (с точностью $O(1)$): имея программу $p$, перерабатывающую х в у, а также любое решение $q$ задачи $(x \to y) \to y$, можно найти у как $[p](q)$.

Докажем теперь, что сложность задачи $((x \to y) \to y) \to (x \lor y)$ не превосходит также $\text{KS}(x|y)$ (с точностью $O(\log n)$). Для этого достаточно установить, что имея тройку, состоящую из $n$, любой программы $p$, преобразующей у в х, и любого решения $q$ задачи $(x \to y) \to y$, можно найти х или у. Пусть $S$ обозначает множество всех слов длины не больше $n$. Как и в предыдущем доказательстве, назовём пару $(u, v) \in S \times S$ согласованной с $q$, если $[q](l_τ) = v$ для всех $τ: S \to S$ таких, что $τ(u) = v$.

Напомним, что у любых двух согласованных с $q$ пар совпадают первые или вторые компоненты. Из этого следует, что либо первые компоненты всех согласованных пар равны х, либо вторые компоненты всех согласованных пар равны у (либо и то, и другое). Действительно, пусть есть пара, у которой первая компонента отличается от х (и потому вторая компонента равна у). Обозначим её $(x', y)$. Пусть есть и пара, у которой вторая компонента не равна у (и потому первая равна х); обозначим её $(x, y')$. Тогда у пар $(x, y')$ и $(x', y)$ различаются обе компоненты, в противоречии со сказанным выше.

Имея $n, p$ и $q$, найдём первую пару $(u, v)$, согласованную с $q$. Затем продолжим поиск других согласованных с $q$ пар и одновременно запустим проверку того, что $[p](v) = u$. Либо то, либо другое обязательно произойдёт: если $[p](v)$ не определено или $[p](v) \neq u$, пара $(u, v)$ отличается от $(x, y)$ и потому есть более одной согласованной пары.

Если мы нашли другую пару $(u', v')$, согласованную с $p$, то при $v \neq v'$ мы знаем $x$ (поскольку тогда $u = u' = x$), а при $u \neq u'$ знаем у (тогда $v = v' = y$). А если мы обнаружили, что $[p](v) = u$, то можем быть уверены, что $u = x$ (если $u \neq x$, то $v = y$ и $x = p(y) = p(v) = u$, противоречие).

Половина утверждения теоремы (неравенство в одну сторону) доказана. Остается доказать, что сложность задачи $((x \to y) \to y) \to (x \lor y)$ не может быть существенно меньше $\min\{\text{KS}(y|x), \text{KS}(x|y)\}$. Пусть нам дана программа $p$, решающая задачу $((x \to y) \to y) \to (x \lor y)$. Имея $p$, мы построим пару программ $(r_1, r_2)$ с таким свойством: либо $r_1$ на входе $x$ выдаёт у, либо $r_2$ на входе у выдаёт $x$ (но при этом мы не будем знать, какой из случаев имеет место). Другими словами, мы предъявляем решение задачи

$$ (((x \to y) \to y) \to (x \lor y)) \to ((x \to y) \lor \tilde{y} \to x)), $$

и этого достаточно для оценки сложности.

Идею построения можно объяснить так. Пусть дана программа $p$, решающая задачу $((x \to y) \to y) \to (x \lor y)$. Нам надо либо преобразовать х в у, либо наоборот. Любое из слов х и у может быть использовано для построения решения
задачи $(x \to y) \to y$. В самом деле, зная $y$, мы можем отображать всё что угодно в $y$. А зная $x$, мы можем из решения задачи $x \to y$ получить $y$.

Получив (исходя из $x$ или исходя из $y$) решение задачи $(x \to y) \to y$, мы можем применить к нему программу $p$ и получить решение задачи $x \lor y$, то есть найти $x$ или $y$. Было бы здорово, если бы $p$ выдавала $y$, если мы начинали с $x$, или, наоборот, $p$ выдавала $x$, если мы начинали с $y$. Но какие основания у нас на это рассчитывать?

Применим технику, известную из теории вычислимости, и рассмотрим пару $A, B$ непересекающихся перечислимых неотделимых множеств. (Неотделимость означает, что не существует разрешимого множества, содержащего одно из множеств $A, B$ и не пересекающегося с другим.) Например, можно взять в качестве $A$ программы без входа, останавливаящиеся с результатом 0, а в качестве $B$ — останавливаящиеся с результатом 1. (См., например, [175].) Удобно считать, что элементами $A$ и $B$ являются натуральные числа.

Для каждого числа $i$ и для любых двух слов $u, v$ рассмотрим программу $q_i(u, v)$, которая действует на входе $s$ следующим образом. (Вход $s$ мы рассматриваем как программу.)

$$ q_i(u, v) \text{ на входе } s: \\ i \in A: \text{ выдать } v; \\ i \in B: \text{ выдать } [s](u); \\ [s](u) = v: \text{ выдать } v \text{ (равное } [s](u)) $$

Имеется в виду, что программа $q_i(u, v)$ ждёт выполнения одного из трёх указанных (перед двоеточиями) условий, перечисляя $A$ и $B$ вычисляя $[s](u)$. Заметим, что первые два условия несовместны друг с другом, а третье может пересекаться с первыми двумя — но в этом случае и указанный ответ один и тот же, так что всё согласовано.

Наше построение гарантирует, что:

(1) если $i \in A$, то для любого $u$ программа $q_i(u, y)$ является решением задачи $((x \to y) \to y)$;

(2) если $i \in B$, то для любого $v$ программа $q_i(x, v)$ является решением задачи $((x \to y) \to y)$;

(3) для любого $i$ программа $q_i(x, y)$ является решением задачи $(x \to y) \to y$.

Таким образом, во всех трёх случаях применение программы $p$ к $q_i(u, v)$ позволит получить решение задачи $x \lor y$.

Теперь мы можем описать обещанные программы $r_1$ и $r_2$ и доказать, что либо $r_1$ отображает $x$ в $y$, либо $r_2$ отображает $y$ в $x$, либо и то, и другое. Программа $r_1$ применяет $p$ ко всем $q_i(x, v)$ при всех $i \in B$ и при всех $v$, ожидая появления ответа вида $[1, z]$ для некоторого $z$; как только такой ответ появится, программа останавливается и выдаёт $z$. Аналогичным образом программа $r_2$ применяет $p$ ко всем $a_i(u, y)$ при всех $i \in A$ и при всех $u$, ожидая появления ответа вида $[0, z]$ при некотором $z$, и выдаёт это $z$.

Указанные выше свойства $q_i$ гарантируют, что ответ программ $r_1$ и $r_2$, если только он появится, будет правильным. Остаётся доказать, что хотя бы в одном из случаем ответ-таки появится.
Пусть это не так. Это значит, что $[p](q_i(x, v))$ всегда начинается на 0 (при всех $i \in B$ и при всех $v$), а $[p](q_i(u, y))$ всегда начинается на 1 (при всех $i \in A$ и при всех $u$). В частности, такое происходит при $v = y$ и $u = x$. Вспомним, однако, что $[p](q_i(x, y))$ определено при всех $i$. Таким образом, первая компонента пары $[p](q_i(x, y))$ позволяет тогда отделить $A$ от $B$ разрешимым множеством, что противоречит предположению. ►

Формула, о которой идёт речь в только что доказанной теореме, и так довольно сложная. Но для доказательства теоремы 238 нам понадобиться ещё немного усложнить её, рассмотрев обобщения формул вида $((x \to y) \to y) \to (x \lor y)$. Пусть даны $k \ge 2$ слов, которые мы обозначим $u_1, \dots, u_k$. Пусть также даны два непустых непересекающихся подмножества $I, J$ множества индексов $\{1, \dots, k\}$. Рассмотрим сначала задачу

$$((X \to Y) \to Y) \to Z,$$

где $X$ есть конъюнкция синглетонов $u_i$ по всем $i \in I$ (то есть, попросту говоря, кортеж, состоящий из этих слов), $Y$ — дизъюнкция синглетонов $u_j$ при $j \in J$, а $Z$ — дизъюнкция всех синглетонов $u_1, \dots, u_k$. Например, при $k=2$, $I=\{1\}$, $J=\{2\}$ мы получаем уже рассмотренную задачу $((u_1 \to u_2) \to u_2) \to (u_1 \lor u_2)$. Другой пример (где для наглядности переменные обозначены разными буквами):

$$((x_1 \land x_2 \to y_1 \lor y_2) \to y_1 \lor y_2) \to x_1 \lor x_2 \lor y_1 \lor y_2 \lor z.$$

**Теорема 243.** Сложность задачи $((X \to Y) \to Y) \to Z$ не меньше минимальной из условных сложностей слов $u_i$ при известных остальных словах из $u_1, \dots, u_k$ (с точностью до $O(1)$).

◀ Доказательство будет аналогично предыдущему: мы построим $k$ алгоритмов; при этом для любой программы $p$, решающей задачу $((X \to Y) \to Y) \to Z$, найдётся такое $m$, что $m$-й алгоритм по $p$ и кортежу слов $u_1, \dots, u_k$ с пропущенным словом $u_m$ находит $u_m$.

Алгоритмы эти будут действовать по той же схеме: зная остальные (кроме $u_m$) слова, мы строим решения задачи $(X \to Y) \to Y$ и применяем к ним $p$. Заметим, что если мы знаем все слова за одним исключением, то знаем либо все переменные в $X$ (и тогда знаем решение задачи $X$), либо все переменные в $Y$ (и тогда знаем решение задачи $Y$ — точнее, даже несколько решений, поскольку это дизъюнкция; нам достаточно было бы одного). Может даже случиться, что мы знаем и то, и другое (например, если пропущенная переменная не входит ни в $X$, ни в $Y$). Во всех случаях мы можем (как и раньше) построить решение задачи $(X \to Y) \to Y$ и применить к нему программу $p$. Результатом такого применения будет какое-то слово $u_t$ (в паре с самим номером $t$), и если вдруг окажется, что $t = m$, то мы тем самым восстановили $u_m$. (Здесь мы считаем, что решениями задач $Y$ и $Z$ являются пары вида $[t, u_t]$; формально говоря, дизъюнкцию более чем двух задач мы не определяли явно, и надо было бы говорить о $(u_1 \lor (u_2 \lor \dots (u_{k-1} \lor u_k) \dots)))$, но это по существу то же самое.)

Вопрос только в том, как гарантировать, что (для некоторого $m$) такое событие ($t = m$) произойдёт, и здесь нам снова понадобится техника из общей теории
вычислимости. Вместо перечислимых неотделимых множеств мы рассмотрим диагональную функцию: это такая вычислимая функция $d$, с которой любая вычислимая функция $u$ совпадает хотя бы в одной точке: для всякой вычислимой функции $u$ найдётся $i$, при котором $d(i) \simeq u(i)$, то есть либо $d(i) = u(i)$, либо оба значения $d(i)$ и $u(i)$ не определены. Строится такая функция $d$ диагональной конструкцией: достаточно положить $d(i)$ равным значению $i$-й функции на $i$. (Мы рассматриваем натуральные числа как аргументы диагональной функции.)

Это построение можно выполнить для функций со значениями 0 и 1; тогда функция $d$ задается двумя непересекающимися перечислимыми множествами (пробразами нуля и единицы), и невозможность построить всюду определённую функцию со значениями 0 и 1, всюду отличающуюся от $d$, означает, что эти прообразы неотделимы. Нам понадобится диагональная функция для случая $k$ значений $1, 2, \dots, k$.

Более точно, для любых слов $v_1, \dots, v_k$ и для любого натурального $i$ мы построим программу $q_i(v_1, \dots, v_k)$ с такими свойствами:

(1) для исходных слов $u_1, \dots, u_k$ программа $q_i(u_1, \dots, u_k)$ является решением задачи $(X \to Y) \to Y$ при любом $i$;

(2) если $d(i) = m$, то $q_i(u_1, \dots, u_k)$ останется решением задачи $(X \to Y) \to Y$ и после замены $u_m$ на любое другое слово $v_m$ (то есть значение $q_i(u_1, \dots, u_{m-1}, v_m, u_{m+1}, \dots, u_k)$ является решением задачи $(X \to Y) \to Y$ при любом $v_m$).

Теперь можно описать $m$-алгоритм (пытающийся восстановить $u_m$ по остальным $u_t$): мы запускаем вычисление $d$ на всех входах; как только обнаруживается $i \text{ с } d(i) = m$, мы применяем данную нам программу $p$ ко всем решениям задачи $(X \to Y) \to Y$, имеющим вид $q_i(u_1, \dots, u_{m-1}, *, u_{m+1}, \dots, u_k)$ (вместо звёздочки мы подставляем всевозможные слова — в силу свойства (2) это будут действительно решения). Как только программа $p$ на одном из таких входов выдаст пару вида $[m, *]$, мы останавливаем процесс: второй член этой пары и будет $u_m$.

Корректность ответа гарантируется свойством (2), но надо убедиться, что хотя бы при одном $m$ такой ответ будет получен (ожидание не будет бесконечным). Тут и понадобится свойство диагональной функции. Пусть ни при одном $m$ описанный процесс не даёт ответа. Тогда, в частности, искомого ответа не получится для $q_i(u_1, \dots, u_k)$ при всех тех $i$, при которых $d(i)$ определено. Но в этом случае при всех $i$ мы имеем дело с решением задачи $(X \to Y) \to Y$ в силу свойства (1). Следовательно, $[p](q_i(u_1, \dots, u_k))$ определено при всех $i$ и по предположению является решением задачи $Z$, то есть имеет вид $[t, u_t]$. Безуспешность поиска означает, что первый член пары $t$ всегда отличается от $d(i)$, если $d(i)$ определено. Поскольку значение $t$ является всюду определённой вычислимой функцией от $i$, то мы получаем противоречие с диагональным свойством.

Осталось описать действие программы $q_i(v_1, \dots, v_k)$ (для произвольного числа $i$ и произвольных слов $v_1, \dots, v_k$). Получив на вход $s$, эта программа параллельно делает две вещи:

(1) пытается вычислить $d(i)$;
(2) строит из слов $v_t$ с $t \in I$ предположительное решение задачи $X$, применяет
к нему $s$ и проверяет, что выход $s$ имеет вид $[t, v_t]$ с $t \in J$ (вторая координата
совпадает с элементом набора $v_1, \dots, v_k$ с тем же индексом).

Как только одно из этих событий (включая положительный результат проверки во втором случае) произошло, программа предпринимает такие действия:

• в случае (1), если $d(i)$ определено и равно некоторому $m$:

- если $m \notin I$, то строим из $v_t$ с $t \in I$ предположительное решение задачи $X$, и выдаём результат применения программы $s$ к этому решению в качестве ответа программы $q_i(v_1, \dots, v_k)$ на входе $s$;

- если $m \in I$ (и потому $m \notin J$), выдаём в качестве ответа пару $[t, v_t]$ для некоторого $t \in J$ — для определённости, скажем, для минимального. (При этом ответ не зависит от входа $s$.)

• в случае (2) программа выдаёт пару $[t, v_t]$, являющуюся результатом работы программы $s$.

Остаётся проверить требуемые свойства. Если слова $v_1, \dots, v_k$ совпадают с $u_1, \dots, u_k$, а программа $s$ является решением задачи ($X \to Y \to Y$), то второе событие произойдёт обязательно (если раньше не произойдёт первое); в обоих случаях выход программы $q_i(u_1, \dots, u_k)$ будет решением задачи $Z$. Значит, в этом случае программа $q_i(u_1, \dots, u_k)$ будет решением задачи ($X \to Y \to Y \to Z$).

Пусть теперь $d(i) = m$, все $v_t$, кроме (возможно) $m$-го, совпадают с соответствующими $u_t$, а $s$ является решением задачи ($X \to Y \to Y$). При этом может раньше случиться и то, и другое событие. Но в обоих случаях выход программы $q_i(v_1, \dots, v_k)$ будет решением задачи $Z$. В самом деле, в случае (1) мы не используем значение $v_m$ вообще. В случае (2) мы его можем использовать, но у нас два резона считать ответ правильным (в силу совпадения), и один из них сработает, поскольку лишь одно $v_t$ отличается от $u_t$. ►

При доказательстве теоремы 238 нам понадобится небольшое обобщение дополненного утверждения. Пусть опять имеется кортеж слов $u = u_1, \dots, u_k$. Пусть также имеется некоторое число ($N$) непересекающихся пар подмножеств множества индексов $\{1, \dots, k\}$:

$$I_l \cap J_l = \emptyset, \quad I_l, J_l \subset \{1, \dots, k\}, \quad l = 1, \dots, N.$$

Для каждого $l$ определим задачи $X_l$ и $Y_l$ как раньше, то есть $X_l$ есть конъюнкция синглетонов $u_l$ для $t \in I_l$, а $Y_l$ — дизьюнкция синглетонов $u_l$ для $t \in J_l$. Наконец, пусть $Z$ — дизьюнкция всех синглетонов $u_1, \dots, u_k$. Рассмотрим теперь задачу

$$((X_1 \to Y_1) \to Y_1) \wedge \dots \wedge ((X_N \to Y_N) \to Y_N) \to Z.$$

**Теорема 244.** Сложность этой задачи не меньше минимума условных сложностей слов $u_i$ при известных остальных словах из набора $u_1, \dots, u_k$ (с точностью до $O(1)$).

◄ Доказательство этой теоремы в основном повторяет предыдущее доказательство. Для каждого $l$, каждого натурального $i$ и каждого кортежа $v = v_1, \dots, v_k$,
отличающегося от кортежа $u$ не более чем в одной координате, мы, как и раньше, строим программу $q_h(v)$, которая будет решением задачи

$$ (X_l \to Y_l) \to Y_l, $$

если $d(i)$ определено и равно той координате, где кортежи $u$ и $v$ различаются, или если $v = u$ (в последнем случае неважно, определено ли и чему равно $d(i)$).

При любом $m$ можно рассмотреть следующий алгоритм поиска $u_m$, если дана любая программа $p$ решения задачи

$$ (((X_1 \to Y_1) \to Y_1) \land \dots \land ((X_N \to Y_N) \to Y_N)) \to Z, $$

а также даны все члены кортежа $u$, кроме $m$-го. Применяем программу $p$ к кортежу, состоящему из программ $q_{i1}(v), \dots, q_{iN}(v)$. В качестве $v$ пробуем все кортежи, совпадающие с $u$ во всех координатах, отличных от $m$-й, а в качестве $i$ — все такие натуральные числа, что $d(i) = m$. Если нам повезёт и для хотя бы для одной такой пары $v$, $i$ программа $p$ остановится и выдаст пару с первой компонентой $m$, то мы найдём $u_m$. Как и раньше, диагональное свойство функции $d$ гарантирует, что существует $m$, для которого такие $v$, $i$ обнаружатся (чтобы убедиться в этом, в качестве $v$ мы берём сам кортеж $u$). ►

Пропозициональные формулы, соответствующие задачам, рассмотренным в этой теореме, называются критическими импликациями. А именно, так называются формулы вида

$$ (((P_1 \to Q_1) \to Q_1) \land \dots \land ((P_N \to Q_N) \to Q_N)) \to R, $$

где $R$ есть дизъюнкция переменных $s_1, \dots, s_k$, формулы $P_l$ представляют собой конъюнкции, а $Q_l$ — дизъюнкции каких-то из этих переменных, причём $P_l$ и $Q_l$ не имеют общих переменных при каждом $l$. Критические импликации невыводимы в IPC (что следует из только что доказанной теоремы, а также может быть доказано с помощью моделей Крипке). Более того, они являются универсальными невыводимыми формулами интуиционистского исчисления высказываний (IPC) в следующем смысле:

**Теорема 245.** Для любой невыводимой в интуиционистском исчислении высказываний формулы $\Phi(t_1, \dots, t_m)$ со связками $\wedge, \vee, \to$ существуют число $k$, формулы $T_1, \dots, T_m$ с переменными $s_1, \dots, s_k$ и некоторая критическая импликация $J(s_1, \dots, s_k)$, для которых формула

$$ \Phi(T_1, \dots, T_m) \to J $$

выводима в IPC. При этом формулы $T_1, \dots, T_m$ содержат только связки $\wedge, \vee$.

Доказательство этой чисто логической теоремы Ю. Т. Медведева выходит за рамки нашей книги. Интересующегося читателя мы отсылаем к работе [176], в которой приведено полное доказательство. Используя это утверждение, мы можем наконец доказать теорему 238.
◀ Пусть формула $\Phi(t_1, \dots, t_m)$ невыводима в IPC. По теореме 245 существуют число $k$, формулы $T_1, \dots, T_m$ с переменными $s_1, \dots, s_k$ и связками $\wedge, \vee$ и некоторая критическая импликация $J(s_1, \dots, s_k)$ такие, что формула

$$ \Phi(T_1, \dots, T_m) \rightarrow J $$

выводима в IPC.

Возьмем случайные независимые слова $u_1, \dots, u_k$ длины $n/c$ (константу $c$ подберём позже) и подставим одноэлементные множества, соответствующие этим словарям, вместо переменных в формулы $T_1, \dots, T_m$. Поскольку эти формулы не содержат импликации, мы получим конечные непустые множества слов $X_1, \dots, X_m$. Формула $\Phi(T_1, \dots, T_m) \rightarrow J$ выводима в IPC, поэтому сложность задачи

$$ \Phi(X_1, \dots, X_m) \rightarrow J(u_1, \dots, u_k) $$

ограничена сверху некоторой константой. Теорема 244 гарантирует, что сложность задачи $J(u_1, \dots, u_k)$ не меньше $n/c - O(1)$. Поэтому и сложность задачи $\Phi(X_1, \dots, X_m)$ также не меньше $n/c - O(1)$, что больше $n/(2c)$ при всех достаточно больших $n$.

Осталось понять, почему длины всех слов в $X_1, \dots, X_m$ не превосходят $n$ (при подходящем выборе константы $c$ и при всех достаточно больших $n$). Любое слово из множеств $X_1, \dots, X_m$ может быть получено из слов $u_1, \dots, u_k$ с помощью фиксированного числа применений операции спаривания $v, w \mapsto [v, w]$ и операции спаривания с нулем или единицей. Если длина слова $[v, w]$ ограничена сверху линейной функцией от длин $v, w$, то утверждение очевидно. Ясно, что спаривающие функции с таким свойством существуют. Осталось заметить, что утверждение теоремы инвариантно относительно замены спаривающей функции на другую, поэтому мы можем предполагать, что спаривающая функция обладает этим свойством. ▶

### 13.5. Доказательство варианта теоремы 238 с помощью моделей Крипке

Доказывая теорему 238, мы приняли на веру утверждение теоремы 245. Хотелось бы обойтись без этого: Ан. А. Мучник предложил доказательство близкого утверждения, которое использует лишь существование контрмодели Крипке у невыводимых в IPC формул. (Было бы интересно найти аналогичное прямое доказательство полного варианта теоремы 238; авторам такое доказательство не известно.)

**Теорема 246.** Пусть формула $\Phi(t_1, \dots, t_k)$ со связками $\wedge, \vee, \rightarrow$ невыводима в IPC. Тогда найдется последовательность задач $X_1^n, \dots, X_k^n$ сложности не более $O(n)$, для которой сложность задачи $\Phi(X_1^n, \dots, X_k^n)$ не меньше $n$ при всех достаточно больших $n$.

Разница с теоремой 238 в том, что мы теперь ограничиваем лишь сложность подставляемых множеств (а не длину слов в них). Кроме того, мы не требуем их конечности (напротив, все множества, строящиеся в доказательстве ниже, будут бесконечными).
Пусть $\langle K, \le \rangle$ — конечная модель Крипке, в корне которой ложна данная нам формула $\Phi(t_1, \dots, t_k)$. Объясним, как по этой модели и произвольному числу $n$ построить множества $X_1, \dots, X_k$. (Для краткости мы опускаем верхний индекс $n$, так как в дальнейшем рассуждении $n$ фиксировано.)

Отберём некоторое бесконечное множество длин, включающее нулевую длину, так чтобы любые две различные ненулевые длины сильно различались (скажем, не менее чем вдесятеро) и чтобы все ненулевые отобранные длины были не меньше $2n$. Будем называть такие длины правильными. Распределим правильные длины между мирами модели $K$ так, чтобы каждому миру досталось бесконечное множество длин, причём нулевая длина досталась корню, и чтобы множества длин, сопоставленных каждому миру, были разрешимыми. Будем называть длины, отнесённые к миру $i$ и, длинами из мира $i$, а слова этих длин — словами из мира $i$.

Пусть всё это сделано. Теперь мы можем объяснить, как построить множество $X_i$, подставляемое вместо переменной $t_i$. Оно равно объединению следующих двух множеств слов. Первое состоит из множества всех случайных слов из миров, в которых истинна переменная $t_i$. Второе, обозначаемое $C$, не зависит от $i$ и равно множеству всех пар вида $\langle x, y \rangle$, где $x$ и $y$ — случайные слова из несравнимых миров. В этом доказательстве слово называется случайным, если его сложность не меньше, чем некоторая линейная функция его длины, скажем, не меньше десятой части длины. Случайным словом нулевой длины будем считать пустое.

Если соблюдать формальности, то в определении $C$ вместо пары $\langle x, y \rangle$ следует брать её кол $[x, y]$, а при объединении множеств дописывать нуль или единицу в начало, чтобы элементы разного происхождения не смешивались:

$$ 
\begin{aligned}
C &= \{ \langle x, y \rangle \mid x, y \text{ случайные слова из несравнимых миров} \}, \\
X_i &= \{ 0x \mid t_i \text{ истинна в мире } v, \text{ а } x \text{ — случайное слово из мира } v \} \cup \\
    &\quad \cup \{ 1y \mid y \in C \}.
\end{aligned}
$$

Поскольку слова из разных миров имеют разные длины, по любому слову из $X_i$ можно понять, из каких миров взялись составляющие его слова.

Мы докажем индукцией по построению формулы $\Psi$ от переменных $t_1, \dots, t_k$, что множество решений задачи $\Psi(X_1, \dots, X_k)$ по существу совпадает с множеством $X_\Psi$, которое определяется по тому же правилу, что и значения переменных. По определению $X_\Psi$ есть множество случайных слов из миров, в которых истинна формула $\Psi$, к которому ещё добавлено $C$ (соблюдая те же формальности, что и при определении $X_i$). Точнее, мы докажем, что $\Psi(X_1, \dots, X_k)$ отличается от $X_\Psi$ алгоритмическим преобразованием: для каждой формулы $\Psi$ существуют две вычислимых функции $f, g$: первая преобразует любое решение задачи $\Psi(X_1, \dots, X_k)$ в некоторый элемент $X_\Psi$, а вторая преобразует любой элемент множества $X_\Psi$ в некоторое решение задачи $\Psi(X_1, \dots, X_k)$.

Если $\Psi$ есть переменная, то множества $\Psi(X_1, \dots, X_k)$ и $X_\Psi$ совпадают и обе функции тождественны. Поэтому достаточно доказать, что для множеств вида $X_\Psi$ операции над задачами коммутируют с одноименными операциями над формулами:

(А) множество $X_\Psi \lor X_\Theta$ алгоритмически эквивалентно множеству $X_{\Psi\lor\Theta}$;

(Б) множество $X_\Psi \land X_\Theta$ алгоритмически эквивалентно множеству $X_{\Psi\land\Theta}$;
(В) множество $X_\Psi \to X_\Theta$ алгоритмически эквивалентно множеству $X_{\Psi \to \Theta}$.

Кроме этого, нам нужна ещё устойчивость логических операций над задачами относительно алгоритмической эквивалентности, то есть, такое свойство: если множества $U, V$ алгоритмически эквивалентны соответственно $U', V'$, то множество $U \lor V$ алгоритмически эквивалентно множеству $U' \lor V'$ (и аналогичное свойство для других двух операций). Эти свойства очевидны, и мы переходим к доказательству (А), (Б) и (В).

(А) По определению $X_\Psi \lor \Theta$ есть объединение множеств $X_\Psi$ и $X_\Theta$, поэтому по любому элементу $X_\Psi \lor X_\Theta$ легко указать некоторый элемент из $X_\Psi \lor \Theta$. В обратную сторону: если нам дан элемент объединения $X_\Psi$ и $X_\Theta$, то можно разобраться, какому из двух множеств он принадлежит и преобразовать его в соответствующий элемент множества $X_\Psi \lor X_\Theta$.

(Б) По определению $X_\Psi \land \Theta$ есть пересечение множеств $X_\Psi$ и $X_\Theta$, а $X_\Psi \land X_\Theta$ есть их декартово произведение. По любому элементу х из пересечения легко найти некоторый элемент декартова произведения, а именно $[x, x]$. В обратную сторону: пусть нам дан элемент $[x, y]$ из декартова произведения $X_\Psi$ и $X_\Theta$. Если хотя бы одно из слов х, у принадлежит С, то оно принадлежит и пересечению этих множеств. Пусть ни одно из них не принадлежит С, то есть х, у — это случайные слова из миров u, v, в которых истинны соответственно Ψ и Θ. Тогда эти миры мы можем найти.

Далее рассмотрим два случая.

(1) Эти миры несравнимы. Тогда мы просто выдаем пару $[x, y]$, которая по определению принадлежит С, а значит, и пересечению $X_\Psi$ и $X_\Theta$.

(2) Миры u, v сравнимы, скажем, u предшествует v. Тогда в силу монотонности истинности, формула Ψ истинна также в мире v, а значит слово у принадлежит пересечению $X_\Psi$ и $X_\Theta$.

(В) Это наиболее интересный случай. Нам надо доказать, что по любому элементу из $X_{\Psi \to \Theta}$ можно найти некоторый элемент $X_{\Psi \to X_\Theta}$ и, обратно, по любому элементу из $X_{\Psi \to X_\Theta}$ можно найти некоторый элемент $X_{\Psi \to \Theta}$. Сначала докажем первое утверждение.

Пусть нам дано слово х из $X_{\Psi \to \Theta}$. Нам надо найти некоторое решение задачи $X_\Psi \to X_\Theta$. По-другому можно сказать так: нам надо, имея х и любое слово у из $X_\Psi$, найти некоторое слово из $X_\Theta$. Если хотя бы одно из слов х, у принадлежит С, мы выдаём это слово. Пусть ни одно из них не принадлежит С. Тогда х — случайное слово из некоторого мира u, в котором истинна формула Ψ → Θ, а слово у — случайное слово из некоторого мира v, в котором истинна формула Ψ (и эти миры мы можем найти, изучив длины х, у). Рассмотрим три случая.

(1) Если мир v предшествует миру u, то формула Ψ истинна и в мире u, следовательно, и формула Θ истинна в мире u (напомним, что импликация $\Psi \to \Theta$ истинна в мире u). Значит, слово х принадлежит множеству $X_\Theta$.

(2) Если мир u предшествует миру v, то формула Θ истинна в мире v, по-скольку в нём истинна формула Ψ и импликация $\Psi \to \Theta$ истинна в мире u. Значит, слово у принадлежит множеству $X_\Theta$.

(3) Если миры u и v несравнимы, то пара $[x, y]$ принадлежит С, а следовательно, и $X_\Theta$.
Осталось доказать, что по любому элементу из $X_\Psi \to X_\Theta$ можно найти некоторый элемент $X_{\Psi\to\Theta}$. Пусть нам дана программа $r$, преобразующая любое слово из $X_\Psi$ в некоторое слово из $X_\Theta$.

Если формула $\Psi \to \Theta$ истинна в корне, то пустое слово принадлежит $X_{\Psi\to\Theta}$ и мы выдаем его.

Пусть формула $\Psi \to \Theta$ ложна в корне. Тогда существует мир $u$, в котором истинна формула $\Psi$, но ложна $\Theta$. Выберем правильную длину $l$ из мира $u$, значительно большую длины программы $r$. Мы знаем, что в применении ко всем случайным словам длины $l$ программа $r$ остановится и выдаст слово из $X_\Theta$. К сожалению, мы не знаем, какие слова случайны, а какие нет. Поэтому будем применять параллельно программу $r$ ко всем словам длины $l$. Если какое-то слово $s$ получится более чем $2^{l/2}$ раз в качестве выхода $r$, то мы нашли нужное слово. Действительно, неслучайных слов длины $l$ значительно меньше, чем $2^{l/2}$, а значит, хотя бы один раз слово $s$ получено как результат работы на случайном слове. Следовательно, слово $s$ принадлежит $X_\Theta \subset X_{\Psi\to\Theta}$.

Попробуем доказать, что найдётся слово, имеющее так много прообразов. Пусть $x$ — случайное слово длины $l$, а $s$ — результат работы программы $r$ на входе $x$. Сложность $s$ не превосходит суммы длин $x$ и $r$ (с логарифмической точностью), и поэтому значительно меньше $2l$. Кроме того, $s$ принадлежит $X_\Theta$, а, следовательно, имеет вид вид $0t$ или $1[y, z]$, где $t, y, z$ — случайные слова разрешённых длин. Поэтому длины $t, y, z$ не могут быть больше $l$. Более того, длина $t$ должна быть строго меньше $l$, так как слово $t$ принадлежит миру, в котором истинна $\Theta$, и этот мир не равен $u$ (напомним, что $\Theta$ ложна в $u$). Значит длина $t$ не больше $l/10$. Кроме того, слова $u$ и $z$ имеют разные длины, поскольку находятся в несравнимых мирах, следовательно одна из них должна быть не больше $l/10$. Если бы и другая длина тоже была всегда не больше $l/10$, то множество результатов работы программы $r$ на случайных входах имело бы мошность значительно меньше $2^{l/2}$. А следовательно, какое-то слово имело бы более $2^{l/2}$ прообразов.

Поскольку всё-таки длина одного из слов $u, z$ может быть равна $l$, мы не можем гарантировать наличия слова с таким количеством прообразов. Тем не менее, наши рассуждения доказывают следующее. Либо некоторое слово $s$ имеет более $2^{l/2}$ прообразов, либо верно следующее: найдётся такое слово $u$, что для более чем $2^{l/2}$ слов $x$ длины $l$ программа $r$ на входе $x$ выдаёт слово вида $1[u, z]$ (или $1[z, y]$), где длина $z$ равна $l$. (Для разных входов $x$ слово $z$ может быть разным.) В этом случае у обязано быть случайным словом из некоторого мира, несравнимого с $u$. Действительно, хотя бы одно из слов $x$, на которых $r$ выдаёт результат $1[u, z]$ (или $1[z, y]$) случайно, а значит, результат работы $r$ должен принадлежать $X_\Theta$. А это может быть только когда у и $z$ случайны и принадлежат несравнимым мирам. Поскольку слово $z$ принадлежит миру $u$ (его длина равна $l$), слово $u$ принадлежит миру, несравнимому с $u$.

Применяя параллельно программу $r$ ко всем словам длины $l$, найдём такое слово $s$ или такое $u$. Если реализовался первый случай и найдено слово $s$ с большим числом прообразов, то оно принадлежит $X_\Theta \subset X_{\Psi\to\Theta}$.

Во втором случае поступим следующим образом. У нас есть случайное слово $u$ из некоторого мира $v$, несравнимого с $u$. Если в мире $v$ истинна формула $\Psi \to \Theta$,
то слово у и есть искомое. Иначе существует мир $u_1$ выше мира $v$, в котором истинна формула $\Psi$, но ложна $\Theta$, и можно повторить все рассуждения для этого мира. В результате либо мы найдём некоторое слово из $X_\Theta$, либо найдём случайное слово из некоторого мира $v_1$, несравнимого с миром $u_1$. При этом мир $v_1$ не может быть ниже $v$ (в этом случае он был бы и ниже $u_1$). Значит, мир $v_1$ либо несравним с миром $v$ (в этом случае мы нашли пару случайных слов в несравнимых мирах и можем остановиться), либо строго выше него. Во втором случае (мир $v_1$ строго выше мира $v$), если формула $\Psi \to \Theta$ истинна в мире $v_1$, то можно остановиться. А иначе можно повторить все рассуждения для мира $v_1$. Рано или поздно мы оставимся, поскольку модель конечна и, следовательно, не содержит бесконечных возрастающих последовательностей миров.

Итак, мы доказали, что множество решений задачи $\Phi(X_1, \dots, X_k)$ алгоритмически эквивалентно множеству $X_\Phi$. По условию формула $\Phi$ ложна в корне, поэтому длины всех слов в $X_\Phi$ не меньше $2n$, значит, сложность задачи $\Phi(X_1, \dots, X_k)$ больше $n$. Осталось понять, почему сложности всех множеств $X_i$ можно сделать равными $O(n)$. Можно считать без ограничения общности, что модель $K$ содержит мир, в котором все формулы истинны (Добавим новый мир, который больше всех остальных и в котором все переменные истинны; на истинность формул в корне этот мир не повлияет). Также можно считать, что длина $2n$ правильная и принадлежит этому миру. Тогда множество случайных слов длины $2n$ принадлежит всем $X_i$. ►

### 13.6. Пример задачи, сложность которой не выражается через условные сложности подставленных слов

Мы оценили сложности многих задач, полученных из одноэлементных множеств логическими операциями $\wedge, \vee, \to$. Могло создаться впечатление, что сложность любой задачи, составленной из синглетонов $\{x\}, \{y\}, \dots$ с помощью этих операций, можно выразить через сложности слов х, у, ..., их пар, троек и т.д. Однако это не так. Задача $(x \to z) \wedge (y \to z)$, сложность которой, напомним, примерно равна наибольшей из условных сложностей $KS(z|x), KS(z|y)$, уже находится на грани той области, где это возможно. А именно, для задачи $(a \to c) \wedge (b \to d)$ это уже невозможно, как мы увидим в теореме 247 (см. [173]). Но сначала несколько простых утверждений:

**341** Докажите, что с логарифмической точностью для любых $a, b, c, d$ выполнены неравенства

$$KS((a \to c) \wedge (b \to d)) \le KS(c|a) + KS(d|b),$$

$$KS((a \to c) \wedge (b \to d)) \le KS(d|b, c) + KS(c),$$

$$KS((a \to c) \wedge (b \to d)) \le KS(c|a, d) + KS(d),$$

$$KS((a \to c) \wedge (b \to d)) \ge KS(b, c, d|a) - KS(b|a, c),$$

$$KS((a \to c) \wedge (b \to d)) \ge KS(a, c, d|b) - KS(a|b, d).$$
**342** Найдите последовательность четвёрок слов линейной от $n$ длины, для которых наименьшая из трёх верхних оценок сложности задачи $(a \to c) \wedge (b \to d)$ из задачи 341 превышает наибольшую из двух нижних оценок более, чем на $o(n)$. [Указание. Можно положить $a = d$ и $b = c$, где $a, b$ — независимые случайные слова длины $n$.]

**Теорема 247.** Существует положительное $\delta$ и последовательности четвёрок слов $\tilde{a}_n, \tilde{b}_n, \tilde{c}_n, \tilde{d}_n$ и $\tilde{a}_n, \tilde{b}_n, \tilde{c}_n, \tilde{d}_n$ линейной (от $n$) длины, для которых сложность задачи $(\tilde{a}_n \to \tilde{c}_n) \wedge (\tilde{b}_n \to \tilde{d}_n)$ более чем на $\delta n$ превосходит сложность задачи $(\tilde{a}_n \to \tilde{c}_n) \wedge (\tilde{b}_n \to \tilde{d}_n)$. При этом сложности слов $\tilde{a}_n, \tilde{b}_n, \tilde{c}_n, \tilde{d}_n$ отличаются от сложностей $\tilde{a}_n, \tilde{b}_n, \tilde{c}_n, \tilde{d}_n$ не более чем на $O(\log n)$, и то же самое верно для всех пар, троек и самих четвёрок.

◀ **Геометрическое доказательство.** Начнём с простого замечания. Для четвёрки $\tilde{a}_n, \tilde{b}_n, \tilde{c}_n, \tilde{d}_n$ из условия теоремы оба неравенства из задачи 341, дающие нижнюю оценку сложности задачи $(a \to c) \wedge (b \to d)$, должны быть строгими — разница между левой и правой частями должна быть не меньше $\varepsilon n$. Поэтому начнем с поиска такой четвёрки. А затем мы подберем другую четвёрку с теми же сложностями, для которой эта разница есть $o(n)$.

Будем использовать геометрическую конструкцию, которая нам помогла найти примеры слов, у которых не выделяется общая информация. Возьмем поле из $2^n$ элементов и будем рассматривать точки, прямые и плоскости в трёхмерном аффинном пространстве над этим полем. Всего имеется $2^{3n}$ точек. Количество прямых примерно равно $2^{4n}$ (прямая задётся парой различных точек — $2^{6n}$ вариантов, причем каждая прямая таким образом может быть задана примерно $2^{2n}$ способами, так как содержит $2^n$ точек). Количество плоскостей примерно равно $2^{3n}$ (плоскость задётся тремя точками — $2^{9n}$ вариантов, а поскольку каждая плоскость содержит $2^{2n}$ точек, она содержит примерно $2^{6n}$ троек точек). В качестве $\langle \tilde{a}, \tilde{b} \rangle$ мы возьмём случайную пару различных пересекающихся прямых, $\tilde{c}$ будет их точкой пересечения, а $\tilde{d}$ — плоскостью, в которой обе они лежат. Нетрудно посчитать, что для этой четвёрки обе нижние оценки из задачи 341 равны $n$ (с точностью до $O(\log n)$).

Докажем, что

$$KS(\langle \tilde{a} \to \tilde{c} \rangle \wedge \langle \tilde{b} \to \tilde{d} \rangle) \geq 1,5n$$

(с точностью до $O(\log n)$).

Пусть $\gamma$ есть решение задачи $(\tilde{a} \to \tilde{c}) \wedge (\tilde{b} \to \tilde{d})$, то есть $\gamma$ — это пара программ $\langle \alpha, \beta \rangle$, первая из которых преобразует $\tilde{a}$ в $\tilde{c}$, а вторая — $\tilde{b}$ в $\tilde{d}$. Рассмотрим множество $S$, состоящее из всех пар различных пересекающихся прямых $a, b$, для которых программа $\alpha$ преобразует $a$ в общую точку $a$ и $b$, а программа $\beta$ преобразует $b$ в плоскость, содержащую $a$ и $b$. При известных $\alpha, \beta$ и $n$ мы можем перечислять все элементы $S$. Так как пара $\langle \tilde{a}, \tilde{b} \rangle$ принадлежит $S$, мы можем заключить, что

$$7n \leq KS(\tilde{a}, \tilde{b}) \leq KS(\gamma) + \log|S|$$

(с точностью $O(\log n)$). Таким образом, нам достаточно доказать, что количество пар в $S$ не превосходит $O(2^{5.5n})$. Это вытекает из следующей комбинаторной леммы.
**Лемма.** Пусть $f$ — некоторая функция, сопоставляющая каждой прямой не-
которую точку на этой прямой, а $g$ — некоторая функция, сопоставляющая
каждой прямой некоторую плоскость, содержащую эту прямую. Пусть множе-
ство $S$ состоит из всех пар прямых $\langle a, b \rangle$ таких, что точка $f(a)$ принадлежит
$b$, а плоскость $g(b)$ содержит $a$. Тогда $S$ содержит не более $O(2^{5,5n})$ пар.

Доказательство. Сначала посмотрим, какая оценка получится, если не при-
бегать к хитростям. Для каждой прямой $b$ существует примерно $2^{2n}$ прямых $a$ в
плоскости $g(b)$, поэтому мощность $S$ не более чем в $2^{2n}$ раз превосходит количе-
ство прямых $2^{4n}$, что даёт верхнюю оценку $|S| \le 2^{6n}$. Такую же оценку мы получим,
если для каждой прямой $a$ подсчитаем количество прямых $b$, проходящих через
$f(a)$. Заметим, что в первом подсчёте мы не использовали того, что прямая $b$
должна содержать точку $f(a)$, а во втором — того, что прямая $a$ должна лежать в
плоскости $g(b)$. Наш план таков: мы модифицируем первое из рассуждений, показ-
зав, что в $S$ в среднем на каждую прямую $b$ приходится не более $2^{1,5n}$ прямых $a$.
При этом мы уже будем учитывать условие $f(a) \in b$. (Можно действовать и симме-
тричным образом — показать, что в $S$ в среднем на каждую прямую $a$ приходится
не более $2^{1,5n}$ прямых $b$.)

Разобьём $S$ на слои, поместив в один слой пары $\langle a, b \rangle$ с одинаковым значением $g(b)$. Все пары данного слоя лежат в одной плоскости, а сам слой однозначно задаётся этой плоскостью. Мы ограничим сверху количество пар в каждом слое, а затем просуммируем полученные оценки. Итак, фиксируем плоскость $d$ и оценим сверху количество пар в $S$, лежащих в слое, соответствующем $d$.

Для этого рассмотрим произвольную точку $c$ на плоскости $d$ и обозначим через $A_c$ множество прямых $a$ в плоскости $d$ с $f(a) = c$, а через $B_c$ — множество прямых $b$, содержащих точку $c$, для которых $g(b) = d$ (из условия следует, что прямая $a$ содержит точку $c$, а прямая $b$ содержится в плоскости $d$). Ясно, что размер слоя не превосходит

$$ \sum_c |A_c| |B_c| \le \sqrt{\sum_c |A_c|^2 \sum_c |B_c|^2} $$

(мы применили неравенство Коши). Обе суммы под корнем легко ограничить свер-
ху, поскольку они имеют ясный смысл. А именно, $\sum_c |A_c|^2$ пропорционально ве-
роятности того, что для двух равномерно и независимо выбранных прямых $a', a''$
в плоскости $d$ будет выполнено $f(a') = f(a'')$. Действительно, вероятность это-
го события есть сумма по всем $c$ вероятности пересечения независимых событий
$f(a') = c$ и $f(a'') = c$. Вероятности этих событий равны между собой и равны
отношению мощности $A_c$ к общему количеству прямых в плоскости $d$, примерно
равному $2^{2n}$. С другой стороны, вероятность события $f(a') = f(a'')$ не превосходит
примерно $2^{-n}$ (при любом фиксированном $a'$ вероятность события $f(a') = f(a'')$ не превосходит вероятности того, что прямая $a''$ проходит через точку $f(a')$, что примерно равно $2^{-n}$). Поэтому $\sum_c |A_c|^2$ не превосходит примерно

$$ (2^{2n})^2 \cdot 2^{-n} = 2^{3n}. $$

Все эти подсчёты верны с точностью до мультипликативной константы.
Вторая сумма $\sum_c |B_c|^2$ связана со средним количеством общих точек у двух равномерно и независимо выбранных прямых $b'$, $b''$ в множестве $M_d$, состоящем из всех прямых $b$, для которых $g(b) = d$ (все они лежат в плоскости $d$). Действительно, среднее количество общих точек $b'$ и $b''$ равно сумме по всем с вероятности того, что точка с принадлежит одновременно $b'$ и $b''$. События $c \in b'$ и $c \in b''$ независимы и вероятности их равны между собой и равны отношению мощности $B_c$ к общему количеству прямых в $M_d$. Поэтому среднее количество общих точек у $b'$ и $b''$ равно отношению суммы $\sum_c |B_c|^2$ к квадрату мощности $M_d$. С другой стороны, поскольку любые две прямые имеют не более одной общей точки или совпадают (что бывает с вероятностью $1/|M_d|$), среднее количество общих точек не превосходит $1 + 2^n/|M_d|$. Поэтому

$$ \sum_c |B_c|^2 \le |M_d|^2 (1 + 2^n / |M_d|) = |M_d|^2 + |M_d| 2^n \le (|M_d| + 2^n)^2. $$

Напомним, что количество пар в слое, задаваемом плоскостью $d$, не превосходит $\sqrt{\sum_c |A_c|^2 \sum_c |B_c|^2}$, поэтому оно не больше

$$ \sqrt{2^{3n} (|M_d| + 2^n)^2} = 2^{1.5n} (|M_d| + 2^n) $$

(с точностью до умножения на постоянный множитель).

Осталось просуммировать полученные оценки по всем $d$:

$$ |S| \le 2^{1.5n} \sum_d (|M_d| + 2^n) = 2^{1.5n} \left( \sum_d |M_d| + \sum_d 2^n \right). $$

Семейства прямых $M_d$ образуют разбиение множества всех прямых, следовательно, сумма мощностей $M_d$ равна общему количеству прямых $2^{4n}$. Кроме того, количество различных плоскостей $d$ примерно равно $2^{3n}$, поэтому вторая сумма также примерно равна $2^{4n}$. Лемма, а вместе с ней и нижняя оценка сложности задачи $(\tilde{a} \to \tilde{c}) \wedge (\tilde{b} \to \tilde{d})$, доказана.

Для завершения доказательства теоремы нам достаточно построить другую четвёрку $\langle \tilde{a}, \tilde{b}, \tilde{c}, \tilde{d} \rangle$ с теми же сложностями, что и у $\langle \tilde{a}, \tilde{b}, \tilde{c}, \tilde{d} \rangle$, для которой сложность задачи $(\tilde{a} \to \tilde{c}) \wedge (\tilde{b} \to \tilde{d})$ примерно равна $n$.

Для этого возьмём случайное слово длины $7n$ и разрежем его на 7 блоков $u, v, w, p, q, r, s$ длины $n$. Положим $\tilde{a} = uvws, \tilde{b} = pqrs, \tilde{c} = ups, \tilde{d} = vqs$. Нетрудно проверить, что сложности слов обеих четвёрок, их пар и т. д. одинаковы и равны:

$$ KS(a) = KS(b) = 4n, \quad KS(c) = KS(d) = 3n, $$

$$ KS(a, b) = 7n, $$

$$ KS(a, c) = KS(a, d) = KS(b, c) = KS(b, d) = KS(c, d) = 5n, $$

$$ KS(a, c, d) = KS(b, c, d) = 6n, $$

$$ KS(a, b, c) = KS(a, b, d) = KS(a, b, c, d) = 7n. $$

При этом сложность задачи $(\tilde{a} \to \tilde{c}) \wedge (\tilde{b} \to \tilde{d})$ примерно равна $n$, поскольку, зная побитовую сумму слов $p$ и $v$ (по модулю 2), можно $\tilde{a}$ преобразовать в $\tilde{c}$, а $\tilde{b}$ в $\tilde{d}$.
**Вероятностное доказательство.** Мы опять начнём с предъявления четверки $\tilde{a}_n, \tilde{b}_n, \tilde{c}_n, \tilde{d}_n$ для которой разница между сложностью задачи $(\tilde{a}_n \to \tilde{c}_n) \wedge (\tilde{b}_n \to \tilde{d}_n)$ и нижними оценками из задачи 341 линейно растет как функция от $n$.

Фиксируем $n$. Мы определим четвёрку слов $\langle \tilde{a}, \tilde{b}, \tilde{c}, \tilde{d} \rangle$ длины $n$, сложности которых примерно равны $n$, сложности всех пар, составленных из них, — примерно $2n$, сложности всех троек, а также сложность самой четвёрки — примерно $3n$. Из этого следует, что обе нижнии оценки задачи 341 близки к $n$. Но для определенной нами четвёрки сложность задачи $(\tilde{a} \to \tilde{c}) \wedge (\tilde{b} \to \tilde{d})$ будет близка к $2n$.

Для построения такой четвёрки рассмотрим всевозможные функции $Q$, отображающие каждую тройку $\langle a, b, c \rangle$ слов длины $n$ в некоторое слово $d$ той же длины.

**Лемма.** Для всех достаточно больших $n$ найдется такая функция $Q$ сложности $\log n + O(1)$, что для не менее чем половины троек $\langle a, b, c \rangle$ слов длины $n$ сложность задачи $(a \to c) \wedge (b \to Q(a, b, c))$ не меньше $2n - O(\log n)$.

Прежде чем доказывать эту лемму, объясним, как из неё будет следовать утверждение теоремы. Выберем функцию $Q$, удовлетворяющую утверждению леммы. Тогда для не менее чем половины троек $\langle a, b, c \rangle$ выполнено неравенство

$$KS((a \to c) \wedge (b \to Q(a, b, c))) \ge 2n - O(\log n).$$

Поэтому найдётся такая тройка сложности не меньше $3n - 1$. Возьмем в качестве $\langle \tilde{a}, \tilde{b}, \tilde{c} \rangle$ любую такую тройку и положим $\tilde{d} = Q(\tilde{a}, \tilde{b}, \tilde{c})$. Сложность четвёрки и сложность тройки $\langle \tilde{a}, \tilde{b}, \tilde{c} \rangle$ будут равны примерно $3n$, как мы и хотели. Поэтому случайны и все пары, составленные из $\tilde{a}, \tilde{b}, \tilde{c}$, и сами $\tilde{a}, \tilde{b}, \tilde{c}$.

Кроме того, из сказанного следует, что и тройка $\langle \tilde{b}, \tilde{c}, \tilde{d} \rangle$ случайна. Действительно, сложность задачи $(\tilde{a} \to \tilde{c}) \wedge (\tilde{b} \to \tilde{d})$ не меньше $2n$ и ограничена сверху суммой $KS(\tilde{c}) + KS(\tilde{d} | \tilde{b}, \tilde{c}) \le 2n$. Следовательно, оба слагаемых в этой сумме примерно равны $n$, то есть слово $\tilde{d}$ независимо от пары $\langle \tilde{b}, \tilde{c} \rangle$. А поскольку сама пара $\langle \tilde{b}, \tilde{c} \rangle$ случайна, то случайна и тройка $\langle \tilde{b}, \tilde{c}, \tilde{d} \rangle$. Единственное, что нам нужно, но не следует из сказанного, это случайность двух оставшихся троек $\langle \tilde{a}, \tilde{b}, \tilde{d} \rangle$ и $\langle \tilde{a}, \tilde{c}, \tilde{d} \rangle$. Как добиться этого, мы обсудим позднее.

**Доказательство.** Переходя к доказательству леммы, определим некоторое алгоритмически проверяемое свойство функции $Q$, которое гарантирует, что для большинства троек $\langle a, b, c \rangle$ сложность задачи $(a \to c) \wedge (b \to Q(a, b, c))$ не меньше $2n - O(\log n)$. Затем мы докажем, что вероятность того, что случайная функция $Q$ обладает этим свойством, положительна. Зная $n$, перебором можно найти функцию $Q$ с таким свойством, поэтому первая найденная функция будет иметь сложность порядка $\log n + O(1)$.

Пусть $S$ обозначает множество всех слов длины $n$, и пусть $M$ — некоторое множество пар всюду определённых функций из $S$ в $S$. Скажем, что множество $M$ обслуживает четвёрку $\langle a, b, c, d \rangle \in S^4$, если $f(a) = c$ и $g(b) = d$ для некоторой пары $\langle f, g \rangle \in M$. Упомянутое свойство функции $Q$ состоит в следующем:

$$ \begin{gathered} \text{любое множество } M \text{ пар функций из } S \text{ в } S \text{ мощности менее } 2^k \\ \text{обслуживает менее } 1/8 \text{ четвёрок вида } \langle a, b, c, Q(a, b, c) \rangle. \end{gathered} $$

Число $k$ мы определим позднее; оно будет чуть меньше $2n$. Это свойство гарантирует, что для $7/8$ троек $\langle a, b, c \rangle$ сложность задачи $(a \to c) \wedge (b \to Q(a, b, c))$
больше $k$. Действительно, решениями задачи $(a \to c) \wedge (b \to d)$ являются пары
программ $\langle p, q \rangle$, для которых $[p](a) = c, [q](b) = d$. Для каждой пары программ
$\langle p, q \rangle$ сложности меньше $k$ доопределим любым способом функции $a \mapsto [p](a)$
и $b \mapsto [q](b)$ на всё множество $S$. Рассмотрим получившееся множество $M$ пар
функций. Его мощность меньше $2^k$. Следовательно, $M$ обслуживает не более од-
ной восьмой части троек $\langle a, b, c, Q(a, b, c) \rangle$. А по построению $M$ обслуживает все
четвёрки $\langle a, b, c, d \rangle$, для которых сложность задачи $(a \to c) \wedge (b \to d)$ меньше $k$.
(Как видно, в формулировке свойства мы могли бы взять $1/2$ вместо $1/8$. Зачем
нам нужен этот запас, станет ясно позднее.)

Рассмотрим равномерное распределение на всех функциях $Q$ рассматриваемого
вида. Другими словами, значения $Q(a, b, c)$ независимы друг от друга и равно-
мерно распределены в множестве $S$. Оценим сверху вероятность того, что слу-
чайная функция $Q$ не обладает описанным свойством (нам нужно так подобрать
$k = n - O(\log n)$, чтобы эта вероятность была меньше 1).

Сначала зафиксируем множество $M$ из $2^k$ функций и оценим сверху вероятность того, что оно обслуживает более чем $1/8$ четвёрок. При подсчёте этой вероятности удобно будет разделить тройки $\langle a, b, c \rangle$ на «плохие» и «хорошие». Плохих троек будет меньше $2^{3n-4}$. А для хороших троек $\langle a, b, c \rangle$ мала будет доля тех $d$, для которых четверка $\langle a, b, c, d \rangle$ обслуживается $M$. По закону больших чисел отсюда будет следовать, что доля обслуживаемых четверок $\langle a, b, c, Q(a, b, c) \rangle$, у которых проекция на первые три координаты хорошая, также меньше $1/16$.

Точнее, назовём тройку $\langle a, b, c \rangle$ (а также четвёрку $\langle a, b, c, d \rangle$) плохой, если количество пар $\langle f, g \rangle$ из $M$, для которых $f(a) = c$, больше $|M|2^{-n+4}$ (это свойство не зависит от $b$ и $d$). Поскольку для каждой пары $\langle f, g \rangle$ из $M$ существует лишь $2^{2n}$ троек вида $\langle a, b, f(a) \rangle$, количество плохих троек меньше $|M| \cdot 2^{2n}/(|M|2^{-n+4}) = 2^{3n-4}$; остальные будут хорошими.

Для любой хорошей тройки $\langle a, b, c \rangle$ вероятность того, что множество $M$ об-
служивает четвёрку $\langle a, b, c, Q(a, b, c) \rangle$, не превосходит $1/32$. Действительно, если
$M$ обслуживает четвёрку $\langle a, b, c, d \rangle$, то $d$ принадлежит множеству, состоящему
из всех таких $g(b)$, что для некоторой функции $f$ пара $\langle f, g \rangle$ принадлежит $M$ и
$f(a) = c$. Это множество содержит не более $2^{-n+4} \cdot |M| = 2^{k-n+4}$ элементов. Сле-
довательно, если выбрать $k$ меньшим $2n-9$, это множество будет содержать менее
чем $(1/32)$-ю часть всех слов длины $n$.

Теперь воспользуемся неравенством Чернова для больших уклонений: если про-
водить $N$ независимых испытаний, вероятность успеха в каждом из которых равна
$p$, то для любого $\epsilon > 0$ доля успешных испытаний будет меньше $p + \epsilon$ с веро-
ятностью не менее $1 - e^{-2\epsilon^2 N/2}$. Мы будем применять следующее его следствие,
получаемое при $\epsilon = p$: если вероятность успеха в отдельном испытании не превос-
ходит $p$, то вероятность того, что доля успешных испытаний больше $2p$, меньше
$e^{-2p^2 N}$. В нашем случае испытания нумеруются хорошими тройками $\langle a, b, c \rangle$, так
что $(15/16)2^{3n} \le N \le 2^{3n}$. Испытание с номером $\langle a, b, c \rangle$ заключается в случайном
выборе $d$, а успехом является то, что четвёрка $\langle a, b, c, d \rangle$ обслуживается множе-
ством $M$. Вероятность успеха не больше $p = 1/32$. Поэтому при случайном выборе
функции $Q$ с вероятностью не менее $1 - e^{-\Omega(2^{3n})}$ для не более чем $1/16$-й части хо-
роших троек $\langle a, b, c \rangle$ соответствующая четвёрка $\langle a, b, c, Q(a, b, c) \rangle$ обслужена $M$.
Если доля обслуженных среди хороших четвёрок не больше 1/16, то даже если все плохие четвёрки обслужены, общая доля обслуженных четвёрок не больше $1/16 + 1/16 = 1/8$. Поэтому вероятность того, что количество обслуженных четвёрок $\langle a, b, c \rangle, Q(a, b, c)\rangle$ больше $2^{3n-3}$, меньше $2^{-\Omega(2^{3n})}$.

Осталось убедиться, что эта вероятность даже при умножении на количество различных множеств $M$ мощности $2^k$ остаётся малой. Количество множеств $M$ не превосходит квадрата количества функций, отображающих слова длины $n$ в слова длины $n$ (оно равно $2^{n2^k}$), возведённого в степень $2^k$. Получается формула

$$2^{2n2^n} = 2^{2^{n+k}+\log n+1}.$$

Сравним эту формулу с формулой для вероятности того, что доля обслуженных четвёрок больше 1/8. При перемножении этих формул показатели экспонент первого этажа складываются и нам нужно чтобы отрищательное слагаемое $-\Omega(2^{3n})$ было больше положительного $2^{n+k+\log n+1}$ по абсолютной величине. Для этого достаточно положить $k = 2n - \log n - O(1)$. (Напомним, что для того, чтобы было мало плохих троек, нам достаточно, чтобы $k$ было меньше $2n-9$, так что наши подсчёты остаются верными.) Лемма доказана.

Теперь надо объяснить, какими свойствами функции $Q$ будет обеспечена слушайность двух оставшихся троек $\langle \tilde{a}, \tilde{b}, \tilde{d} \rangle$, $\langle \tilde{a}, \tilde{c}, \tilde{d} \rangle$. Самое простое — это действовать так же, как в доказательстве случайности тройки $\langle b, \tilde{c}, \tilde{d} \rangle$. Для этого нам нужно, чтобы для половины троек $\langle a, b, c \rangle$ сложной была не только задача $(a \to c) \wedge (b \to d)$, но также и симметричные ей задачи $(c \to b) \wedge (a \to d)$ и $(b \to a) \wedge (c \to d)$. А для этого надо ужесточить требования к функции $Q$, добавив два новых условия, симметричных предыдущим:

**Лемма.** Для всех достаточно больших $n$ найдётся такая функция $Q$ сложности $\log n + O(1)$, что для половины троек $\langle a, b, c \rangle$ слов длины $n$ сложность каждой из трёх задач $(a \to c) \wedge (b \to Q(a, b, c))$, $(c \to b) \wedge (a \to Q(a, b, c))$, $(b \to a) \wedge (c \to Q(a, b, c))$ больше $2n - O(\log n)$.

**Доказательство.** Предыдущая лемма доказывалась вероятностным методом: мы рассмотрели некоторое свойство функции $Q$ и доказали, что для случайной функции оно не выполнено с экспоненциально малой вероятностью. Теперь вместо одного свойства надо рассмотреть три симметричных свойства. Каждое из них также не выполнено с экспоненциально малой вероятностью. Поэтому для всех достаточно больших $n$ найдётся функция, обладающая всеми тремя свойствами. Для такой функции количество троек, не обслуживаемых каким-то из трех симметричных способов, меньше $1/8 + 1/8 + 1/8 < 1/2$. Лемма доказана.

Для завершения второго доказательства теоремы осталось предъявить другую четвёрку с теми же сложностями, что и у построенной, но для которой сложность задачи $KS((a \to c) \wedge (b \to d))$ существенно меньше, чем $2n$. Для этого возьмём случайное слово длины $3n$, разрежем его на три части длины $n$. Это будут $a, b$ и $c$; затем положим $d = a \oplus b \oplus c$. Зная $a \oplus c$, мы можем по $a$ найти $c$, а по $b$ найти $d$, следовательно $KS((a \to c) \wedge (b \to d)) = n$ (с точностью до константы). ►

**343** Докажите, что сложность задачи $(p \lor q) \to (r \lor s)$ также не выражается через сложности $p, q, r, s$, их пар, троек, и четвёрки. [Можно положить $p = a$,
$q = b, r = ac, s = bd$, где $\langle a, b, c, d \rangle$ — одна из двух четвёрок, использованных в доказательстве теоремы (скажем, в первом). Сложность полученной задачи зависит от того, какую из двух четвёрок взять, а сложности $p, q, r, s$, их пар, троек, и четвёрки не зависят от этого.]

Полезно сравнить вероятностное доказательство с геометрическим. Геометрическое доказательство более конструктивно — в нем первая четвёрка задана более явно, чем в вероятностном доказательстве. Зато в вероятностном доказательстве для первой четвёрки сложность задачи $(a \to c) \land (b \to d)$ равна верхним оценкам из задачи 341, которые все равны $2n$. Для четвёрок из геометрического доказательства эти верхние оценки также все равны $2n$, однако для первой четвёрки мы получили лишь нижнюю оценку $1,5n$ для сложности задачи $(a \to c) \land (b \to d)$. Можно ли получить лучшую оценку, неизвестно.
# 14. Алгоритмическая статистика

## 14.1. Постановка задачи. Дефект случайности.

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

Пусть, скажем, имеется некоторое устройство («чёрный ящик»). Мы включили его, и оно выдало последовательность из миллиона битов (= число от 0 до $2^{1000000} - 1$). Что можно сказать о внутреннем строении «чёрного ящика», зная эту последовательность?

Классическая математическая статистика, увы, про это ничего не говорит. Вот если бы мы имели данные от большого числа одинаковых независимых устройств, или могли включать наше устройство много раз подряд (и предположить, что результаты последовательных включений независимы), тогда другое дело. (Заметим в скобках, что ситуации однократного и невоспроизводимого эксперимента не так уж и редки на практике.) Или, скажем, если бы мы заранее имели некоторое параметрическое семейство гипотез, — тогда можно было бы выбирать максимально правдоподобное значение параметра. А так ничего не скажешь — ведь все $2^{1000000}$ возможных исходов с точки зрения математической статистики совершенно равновремны (на множестве возможных исходов нет никакой структуры).

Тем не менее здравый смысл иногда позволяет выдвинуть кажущиеся разумными предположения. Например, если наше устройство выдало миллион нулей, скорее всего оно только и умеет что выдавать нули. А если оно выдало последовательность нулей и единиц безо всяких закономерностей, то похоже, что это результат миллиона независимых бросаний монеты. И хорошо бы как-нибудь уточнить механизм таких догадок.

В первом примере (слово из одних нулей) мы предлагали в качестве объяснения гипотезу, согласно которой только это слово и могло появиться. Формально говоря, наша гипотеза указывала в качестве множества возможных результатов эксперимента одноэлементное множество, состоящее из слова 00...0. Примерно то же естественно сказать и для любого двоичного слова х малой сложности: можно предположить, что чёрный ящик как раз и предназначен для порождения такого слова (имеет множество возможностей $\{x\}$).

Второй пример (слово без закономерностей, у которого сложность примерно равна длине) указывает другой крайний случай, когда мы говорим, что чёрный ящик мог выдать любое слово, то есть указываем в качестве множества возможностей множество всех слов длины 1 000 000.
Бывают и промежуточные примеры. Пусть оказалось, что первые 500 000 битов нашего слова равны нулю, а дальше идут 500 000 «случайных битов» (то есть некоторое слово длины и сложности 500 000). Видимо, разумная гипотеза в этом случае такова: чёрный ящик устроен так, что он сначала выдаёт 500 000 нулей, а потом уже 500 000 случайно выбранных символов. Соответствующее множество возможностей состоит из всех двоичных слов длины 1 000 000, у которых первая половина состоит только из нулей (таких слов, очевидно, $2^{500 000}$).

Общая схема всех наших примеров такова. Нам дают некоторое слово х. Мы предлагаем в качестве «объяснения» этого слова некоторое множество А, содержащее х. При этом мы хотим, чтобы:

* множество А было простым (колмогоровская сложность А была бы мала);

* слово х было бы «типичным представителем» множества А.

Как уточнить эти пожелания? Чтобы говорить о колмогоровской сложности конечного множества, запишем элементы этого множества в список (заранее договорившись о порядке — скажем, в лексикографическом порядке), этот список закодируем двоичным словом и возьмём сложность этого слова. (Разные естественные способы кодирования дадут варианты сложности, отличающиеся не более чем на константу, поскольку от одного из них можно алгоритмически переходить к другому.)

Понятие «типичного представителя» также можно уточнить в терминах колмогоровской сложности. Вспомним, что если множество А содержит N элементов, то условная сложность $KS(x|A)$ любого его элемента при известном А не превосходит $\log_2 N + O(1)$, поскольку каждый элемент может быть задан своим порядковым номером в множестве А. Большинство элементов множества А имеют условную сложность, близкую к $\log_2 N$ (поскольку элементов меньшей сложности máло по сравнению с N), и типичными представителями множества А можно назвать как раз входящих в это большинство.

Другими словами это можно объяснить так. Назовём (неотрицательную с точностью до константы) величину

$$d(x|A) = \log_2 |A| - KS(x|A)$$

дефектом случайности слова х в множестве А (мы будем использовать это равенство лишь в случае, когда $x \in A$, хотя правая часть имеет смысл всегда; при $x \notin A$ естественно считать, что $d(x|A) = +\infty$, поскольку в этом случае гипотеза А «максимально непригодна» для объяснения слова х). «Типичными представителями» множества А мы считаем те $x \in A$, для которых величина $d(x|A)$ мала.

**[344]** Докажите, что вероятность того, что случайно взятый элемент данного множества А имеет дефект больше k, не превосходит $2^{-k}$.

(Вероятность понимается здесь просто как доля элементов с большим дефектом в множестве А. Чтобы это утверждение было формально верным, надо брать целую часть снизу от $\log_2 |A|$ в определении дефекта, но поскольку сложность по существу определена с точностью до константы, этим можно пренебречь.)

Заметим ещё, что функция d (как функция двух аргументов) перечислима снизу (мы можем постепенно получать всё более точные нижние оценки для неё, хотя и
не можем сказать, когда мы дошли до предела). Это непосредственно следует из того, что функция $KS$ перечислима сверху.

**345** Пусть $\delta(x|A)$ определено для любого элемента $x$ любого конечного множества $A$, причём: (а) функция $\delta$ перечислима снизу; (б) для любого множества $A$ и любого числа $k$ доля элементов $A$, для которых $\delta(x|A) > k$, не превосходит $2^{-k}$. Тогда $\delta(x|A) \le d(x|A) + O(1)$.

Смысл этой задачи (которая является простым следствием аналогичного утверждения для условной сложности, см. теорему 19 на с. 46) можно объяснить так. Могут быть разные мнения о том, какие элементы в каких множествах «нетипичны» (разные способы измерения дефекта). Если мы все их отнормируем по доле нетипичных элементов, потребовав, чтобы доля $k$-нетипичных элементов не превосходила $2^{-k}$, а также будем требовать, чтобы нетипичность можно было рано или поздно алгоритмически обнаруживать, то среди всех способов измерения дефекта существует наилучший (с точностью до константы он обнаруживает не меньше дефектов, чем любой другой).

Другими словами, дефект случайности в конечном множестве можно рассматривать как конечный аналог дефекта случайности для бесконечных последовательностей (раздел 3.5). Точнее, приведённое определение соответствует ограниченному по вероятности дефекту; можно рассмотреть и аналог ограниченного в среднем дефекта, как показывает следующая задача.

**346** Покажите, что префиксный дефект случайности элемента $x$ относительно конечного множества $A$, определяемый как $d_P(x|A) = \log_2|A| - KP(x|A)$, является максимальной перечислимой снизу функцией $\delta$ двух аргументов $(x$ и $A)$, для которой среднее значение $(1/|A|) \sum_{x \in A} 2^{\delta(x|A)}$ не превосходит единицы для любого конечного множества $A$. [Указание: воспользуйтесь описанием условной префиксной сложности как логарифма априорной вероятности.]

Таким образом, задачу поиска хорошего объяснения для данного слова $x$ можно сформулировать так: надо найти простое множество $A$, для которого дефект $d(x|A)$ мал. Всегда ли (для любого ли $x$) это возможно? Этот вопрос мы рассматрим в следующем разделе.

Отметим ещё, что знатоки теории вероятностей могут законно упрекнуть нас в том, что мы рассматриваем лишь равномерные распределения в качестве вероятностных гипотез. Вместо этого можно было бы говорить о произвольных распределениях вероятностей (для простоты — с конечным носителем и рациональными значениями вероятностей) и определять дефект слова $x$ относительно распределения $P$ как $-\log_2 P(x) - KS(x|P)$ (считая его бесконечным для тех $x$, для которых $P(x) = 0$: для таких $x$ объяснение $P$ совсем непригодно).

Для равномерных распределений (все элементы конечного множества имеют вероятность $1/|A|$) это определение совпадает с прежним. Можно заметить, что и в общем случае отличие не слишком велико, как показывает следующая задача:

**347** Пусть для слова $x$ сложности $n$ найдено вероятностное распределение сложности не больше $k$, при котором дефект $x$ не больше $l$. Тогда существует множество $A$ сложности не больше $k + O(\log(l + n))$, содержашее $x$, относительно
но которого дефект х не превосходит $l + O(\log(l + n))$. [Указание. Пусть $p$ — вероятность слова х относительно распределения $P$, округлённая вниз до ближайшей степени двойки. Положим $A = \{y \mid P(y) \ge p\}$.]

Поэтому в дальнейшем мы в основном ограничиваемся конечными множествами (и равномерными распределениями вероятностей на них) в качестве описаний. При этом важно подчеркнуть, что говоря о сложности конечного множества, мы имеем в виду его сложность как конструктивного объекта (писка элементов), а не, скажем, сложность его перечисления (сложность программы, порождающей все его элементы). Если допустить последнее, то определение стохастичности станет неинтересным: любой объект х сложности $n$ содержится в множестве $S_n$ всех объектов сложности не больше $n$, которое имеет $O(2^n)$ элементов и которое можно порождать программой сложности $O(\log n)$, но вряд ли стоит считать $S_n$ хорошим «объяснением» для х.

Аналогичным образом (в определении с мерами) рассматривать сложность мер как конечного объекта (если её значения рациональны) или даже сложность мер с вычислимыми значениями, имея в виду сложность соответствующей программы, но нельзя рассматривать перечислимые снизу меры и сложность программ, приближающих их снизу — ибо в этом случае всякое слово имеет простое объяснение — максимальную перечислимую снизу полумеру.

### 14.2. Стохастические объекты

Будем говорить, что слово х является $(\alpha, \beta)$-стохастическим, если для него существует «хорошее объяснение»: существует конечное множество $A$, содержащее слово х, для которого $KS(A) \le \alpha$ и $d(x|A) \le \beta$.

Возникает такой естественный вопрос: будем рассматривать все слова длины $n$ и положим $\alpha$ и $\beta$ равными $O(\log n)$ или $o(n)$ (тем самым сложность гипотезы, как и полагается, мала по сравнению с длиной объясняемых слов). Будут ли при таких $\alpha$ и $\beta$ существовать нестохастические («необъяснимые») объекты? Да, как показывает следующая теорема.

**Теорема 248.** При $2\alpha + \beta < n - O(\log n)$ существуют слова длины $n$, не являющиеся $(\alpha, \beta)$-стохастическими.

(Точнее: существует такая константа $c$, что для всех достаточно больших $n$ и для всех $\alpha$ и $\beta$ с $2\alpha + \beta < n - c \log n$ существуют слова длины $n$, не являющиеся $(\alpha, \beta)$-стохастическими.)

► Рассмотрим список всех конечных множеств сложности не больше $\alpha$. Сложность такого списка не больше $\alpha + O(\log \alpha) = \alpha + O(\log n)$ (см. с. 36). Для краткости мы будем игнорировать члены порядка $O(\log n)$, надеясь, что читатель к этому уже привык и легко исправит рассуждение; в частности, мы будем считать, что список имеет сложность не больше $\alpha$.

Отберём в этом списке множества, имеющие не более $2^{\alpha+\beta}$ элементов. Результирующий список также имеет сложность $\alpha$ и содержит не более $2^\alpha$ множеств размера $2^{\alpha+\beta}$. Всего в них $2^{2\alpha+\beta} < 2^n$ элементов, и поэтому есть слова длины $n$,
не попадающие в эти множества. Рассмотрим первое такое слово (скажем, в ал-
фавитном порядке). Оно имеет сложность не более $\alpha$, поскольку для его задания
(помимо числа $n$) достаточно знать этот список.

Покажем, что это слово (обозначим его $t$) не может быть $(\alpha, \beta)$-стохастиче-
ским. Если $t$ содержится в некотором множестве $A$ сложности не больше $\alpha$, то
размер этого множества больше $2^{\alpha+\beta}$, поскольку все меньше множества мы ис-
ключили по построению. Тогда $d(t|A) = \log|A| - KS(t|A) \ge (\alpha + \beta) - KS(t) \ge
(\alpha + \beta) - \alpha \ge \beta$.

(Во всех этих построениях нужно, конечно, оставить запас размера $c \log n$ при
достаточном $c$, чтобы компенсировать добавки порядка $O(\log n)$.) ►

С другой стороны имеется следующая очевидная оценка:

**Теорема 249.** Если $\alpha + \beta > n + O(\log n)$, то все слова длины $n$ являются $(\alpha, \beta)$-стохастическими.

◀ Достаточно разбить все слова длины $n$ на $2^\alpha$ множеств размера $2^\beta$. ▶

Как мы увидим, реальная ситуация (с какого момента все слова становятся
стохастическими) ближе к этой нижней оценке, чем к предыдущей верхней (см.
задачу 362 на с. 496).

Естественно поинтересоваться, насколько часто встречаются нестохастические
объекты. Например, можно спросить, какую долю они составляют среди слов дли-
ны $n$. Занаранее ясно, что эта доля не превосходит $2^{-\beta}$, поскольку в множестве $A$,
состоящем из всех слов длины $n$, слова с дефектом $\beta$ составляют долю не бо-
лее $2^{-\beta}$.

С другой стороны, если $2\alpha + \beta$ много меньше $n$, можно продолжить доказатель-
ство теоремы 248, используя имеющийся в нём запас. А именно, для некоторого $h$
можно взять все множества сложности не больше $\alpha$ с числом элементов не больше
$2^{\alpha+\beta+h}$ и затем взять первые $2^h$ элементов, не покрытых этими множествами; та-
кие элементы найдутся, если $2\alpha + \beta + h < n$. Сложность этих элементов будет не
больше $\alpha + h$ и потому их дефект в любом множестве из более чем $2^{\alpha+\beta+h}$ эле-
ментов будет больше $\beta$. Проведя эти рассуждения аккуратно (не забывая о членах
порядка $O(\log n)$), получаем такой результат:

**Теорема 250.** Среди слов длины $n$ доля не-(α, β)-стохастических слов не
меньше $2^{-2\alpha-\beta-O(\log n)}$.

Можно также интересоваться не просто долей нестохастических слов (другими
словами, вероятностью получения такого слова при бросании монеты), а их суммар-
ной априорной вероятностью (вероятностью их получения на выходе оптимальной
вероятностной машины). Формально говоря, пусть $m(x)$ — априорная вероятность
слова $x$ (в смысле главы 4, равная $2^{-KP(x)+O(1)}$). Рассмотрим сумму $m(x)$ по всем
славам длины $n$, не являющимся (α, β)-стохастическими.

**Теорема 251.** Если $2\alpha + \beta < n - O(\log n)$ и $\alpha < \beta - O(\log n)$, то указанная
сумма есть $2^{-\alpha+O(\log n)}$.

◀ Нам нужно указать верхнюю и нижнюю оценку для этой суммы. Нижняя
оценка получается из доказательства теоремы 248; в самом деле, построенное там
нестохастическое слово имеет сложность $\alpha$ и потому уже для него одного априорная вероятность равна $2^{-\alpha}$ (как всегда, мы опускаем слагаемые $O(\log n)$).

Для получения верхней оценки рассмотрим сумму $m(x)$ по всем словам длины $n$. Получится некоторое действительное число $\omega$, не превосходящее единицы. Пусть $\bar{\omega}$ — его приближение снизу с точностью $2^{-\alpha}$ (первые $\alpha$ битов оставляем, остальное выбрасываем). Все слагаемые в сумме $\omega = \sum\{m(x) | l(x) = n\}$ перечислимы снизу; будем строить их рациональные приближения и остановимся, как только суммы этих приближений превысят $\bar{\omega}$.

В результате мы получим некоторую меру $P$ с рациональными значениями на множестве всех слов длины $n$, имеющую сложность $\alpha$ (поскольку она вычислимо строится по слову $\bar{\omega}$ длины $\alpha$). Мера $P$ отличается от априорной вероятности не более чем на $2^{-\alpha}$ (суммарно по всем словам).

Задача 347 позволяет использовать в определении стохастичности произвольные меры (а не только равномерные) с погрешностью $O(\log n)$ в параметрах. Остаётся показать, что суммарная априорная вероятность всех слов, для которых дефект относительно $P$ больше $\beta$, не превосходит $2^{-\alpha}$. В самом деле, для таких слов $x$ мы имеем

$$ - \log P(x) - KS(x|P) > \beta. $$

Сложность $P$ не больше $\alpha$ и потому $KS(x)$ превосходит $KS(x|P)$ не более чем на $\alpha$, откуда

$$ - \log P(x) - KS(x) > \beta - \alpha. $$

Поскольку члены порядка $O(\log n)$ мы игнорируем, можно заменить обычную сложность на префиксную:

$$ - \log P(x) - KP(x) > \beta - \alpha. $$

Вспоминая, что префиксная сложность связана с априорной вероятностью, получаем, что

$$ \log(m(x)/P(x)) > \beta - \alpha $$

для любого слова $x$ с дефектом (относительно $P$) больше $\beta$. По условию $\alpha < \beta$ с запасом, достаточным для компенсации всех допущенных нами ошибок, так что можно считать, что для всех таких слов выполнено неравенство $P(x) < m(x)/2$, или $(m(x) - P(x)) > m(x)/2$. Вспоминая, что сумма $m(x) - P(x)$ по всем вообще $x$ не превосходит $2^{-\alpha}$ по построению меры $P$, заключаем, что и сумма всех $m(x)$ по словам дефекта больше $\beta$ относительно $P$ не превосходит $2^{-\alpha+O(\log n)}$, что и требовалось. ►

Понятие стохастического объекта можно рассматривать как конечный аналог понятия последовательности, случайной по некоторой вычислимой мере. Тут есть не только аналогия, но и прямая связь, как показывает следующая задача.

**348** Покажите, что если последовательность $\omega$ случайна в смысле Мартин-Лёфа относительно некоторой вычислимой меры, то её начальные отрезки длины $n$ являются $(O(\log n), O(\log n))$-стохастическими словами. [Указание: можно воспользоваться определением стохастичности с мерами.]
Выведите отсюда, что существуют последовательности, не случайные в смысле Мартин-Лёфа ни по какой вычислимой мере. [Указание: добавление начального отрезка малой длины не сильно нарушает нестохастичность.]

### 14.3. Двухчастные описания

Можно оценивать качество статистических гипотез и в немного другой системе координат. Начнём с такого замечания. Если слово х является элементом конечного множества А, то можно задать это слово, указав:

* множество А;

* порядковый номер слова х в этом множестве (относительно какого-либо естественного порядка на словах, скажем, алфавитного).

Из этого следует, что $KS(x) \le KS(A) + \log |A|$ для любого элемента х любого конечного множества А (опять же с логарифмической точностью).

Одно и то же слово х может иметь много таких «двухчастных» описаний. Какие из них лучше, какие хуже? Ясно, что вообще-то мы хотели бы сделать обе части описания как можно меньше: если удалось найти более простое множество того же размера или найти меньше множество той же сложности (среди множеств, содержавших х), то это хорошо. Но как сравнивать простое, но большое множество с меньшим, но более сложным? Одна из возможностей — сравнить длины соответствующих двухчастных описаний и предпочтение более короткое. (По-английски этот принцип сравнения называют Minimal Description Length principle, или MDL.)

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

**Теорема 252.** Пусть конечное множество А содержит слово х и $i < \log |A|$. Тогда можно найти конечное множество $A'$, содержащее х, для которого $|A'| \le \frac{|A|}{2^i}$ и $KS(A') \le KS(A) + i + O(\log i)$.

◀ Запишем элементы А в каком-то фиксированном порядке (например, алфавитном) и разобьём их на $2^i$ частей (первые $|A|/2^i$ элементов, следующие и т.д.; мы опускаем очевидные оговорки для случая, когда нацело не делится). В качестве $A'$ возьмём часть, в которую попало слово х. Чтобы задать её, достаточно указать А, число i и номер части, на который нужно не более i битов. ►

Это утверждение удобно иллюстрировать картинкой. Для данного слова х рассмотрим множество $P_x$ всех пар $(k, l)$, при которых существует конечное множество $A \ni x$ с $KS(A) \le k$ и $\log |A| \le l$. Из определения ясно, что вместе с каждой точкой в это множество входят все точки справа от неё (с большими $k$) и все точки сверху от неё (с большими $l$). Только что доказанная теорема показывает, что можно сдвигаться вправо-вниз на вектор $(k, -k)$ (с логарифмической точностью).

Как мы увидим, обратное движение возможно далеко не всегда, так что из двухчастных описаний одной и той же (суммарной) длины более ценным является описание с более простым множеством большего размера (из него можно получить другие, но не наоборот).
Схематически строение множества $P_x$ можно описать так (все утверждения с логарифмической точностью). В него входит точка $\langle 0, l(x) \rangle$, соответствующая множеству $A$ всех слов той же длины, что и $x$. Кроме того, в него входит точка $\langle KS(x), 0 \rangle$, соответствующая $A = \{x\}$. Множество $P_x$ ограничено кривой, идущей от первой точки до второй, причём эта кривая не заходит в треугольник $k + l \le KS(x)$ (пунктирная линия) и всюду идёт вниз под углом $45^\circ$ или более, согласно теореме 252 (рис. 14.1).

<figure><img src="image_52.png" /><figcaption>Рис. 14.1. Множество $P_x$.</figcaption></figure>

При взгляде на рисунок возникает естественный вопрос: какие граничные кривые возможны? Может ли, например, граница области $P_x$ пройти по пунктирной линии? Может, для этого достаточно в качестве $x$ взять случайное слово, к которому приписать недостающие (до желательной длины) нули. Тогда точка $(0, KS(x))$ в начале пунктирной кривой реализуется множеством $A$, состоящим из всех слов, на конце которых стоят эти самые нули. По теореме 252 угол спуска границы $P_x$ не может быть меньше $45^\circ$. А поскольку граница $P_x$ не может опуститься ниже пунктирной кривой, она совпадает с ней (с логарифмической точностью).

Не столь очевиден ответ на другой вопрос: может ли кривая идти под углом $45^\circ$ до самого конца, где круто спускаться из точки $\langle KS(x), l(x) - KS(x) \rangle$ к оси абсцисс (в точке $\langle KS(x), 0 \rangle$), как сплошная линия на рис. 14.2. Неформально говоря, это означает, что слово $x$ допускает по существу лишь два вида статистических гипотез: множество всех слов длины $l(x)$ (и его части, получаемые по теореме 252), и одноэлементное множество $\{x\}$.

**349** Показайте, что в этом случае слово $x$ не будет $(\alpha, \beta)$-стохастическим при $\alpha, \beta$, малых по сравнению с $KS(x)$ и $n - 2KS(x)$.

Оказывается, что возможны не только два крайних случая (они изображены на рис. 14.2), но и все промежуточные: любая (достаточно простая) кривая с указан-
<figure><img src="image_53.png" /><figcaption>Рис. 14.2. Две граничные кривые.</figcaption></figure>

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

**Теорема 253.** Пусть даны $k \le n$ и последовательность

$$n = t_0 > t_1 > \dots > t_k = 0$$

из натуральных чисел, имеющая сложность $m$. Тогда существует слово $x$ сложности $k + O(\log n) + O(m)$ и длины $n + O(\log n)$, для которого множество $P_x$ отстоит от множества $T = \{\langle i, j \rangle \mid (i \le k) \Rightarrow (j \ge t_i)\}$ не более чем на $O(\log n) + O(m)$.

(Говорят, что множество $P$ отстоит от множества $Q$ не более чем на $\varepsilon$, если $P$ содержится в $\varepsilon$-окрестности $Q$ и наоборот.)

Мы уже говорили, что из этой теоремы следует существование нестохасти-
ческих слов. Поэтому не удивительно, что её доказательство использует тот же
приём, что и доказательство теоремы 248.

Для каждого $i$ от 0 до $k$ составим список всех множеств сложности не больше $i$ и размером не больше $2^{t_i}$; объединив все такие множества (при данном $i$), получим некоторое множество $S_i$, состоящее не более чем из $2^{i+t_i}$ элементов. (Здесь и далее при оценке числа элементов мы опускаем постоянные и полиномиальные по $n$ множители, поскольку они соответствуют слагаемым $O(\log n)$ в оценках длин и сложностей.) Поскольку $t_i$ убывают (что соответствует наклону 45° на рисунке), то $i+t_i$ не возрастают с ростом $i$, и потому любое из $S_i$ содержит не более $2^{t_0} = 2^n$ элементов. Объединение всех $S_i$ также содержит не более чем $2^n$ элементов (с точностью до полиномиального множителя), и потому среди слов длины $n$ (точнее, $n + O(\log n)$) есть слово, не входящее ни в одно из множеств $S_i$. Первое (в каком-либо, например, алфавитном порядке) такое слово и будет искомым словом $x$.
По построению $P_x$ лежит выше кривой $t_i$ (содержится в множестве $T$). Остаётся оценить сложность слова $x$ и показать, что множество $P_x$ прилегает к кривой (то есть что $T$ содержится в окрестности $P_x$).

Верхняя оценка сложности слова $x$ следует из того, что список всех объектов сложности не больше $k$ с указанием их сложности имеет сложность $k + O(\log k)$ (достаточно знать $k$ и самую долгоиграющую программу длины не больше $k$, см. с. 36); помимо этого списка нам надо знать последовательность $t_0, t_1, \dots, t_k$, имеющую сложность $m$.

Нижняя оценка: меньше $k$ сложность слова $x$ быть не может, так как все одноэлементные множества такой сложности выброшены.

Остаётся показать, что при любом $i \le k$ слово $x$ можно поместить в множество $A$ сложности $i$ (или чуть больше) и размера $2^{t_i}$ (или чуть больше). Искомое множество $A$ строится «с нескольких попыток».

Вначале возьмём первые $2^t$ слов нужной длины в качестве $A$ и параллельно развернём процесс порождения множеств сложности не больше $j$ и размера не больше $2^j$ при всех $j = 0, \dots, k$. Для каждого $j$ получится список множеств, который мы будем называть $j$-списком. В ходе этого процесса будут обнаруживаться подлежащие выбрасыванию слова — элементы всех множеств во всех списках; появление нового множества приводит к одномоментному выбрасыванию всех входящих в него слов. Пока не все слова из $A$ оказались выброшенными (пока объединение порождённых множеств не покроет целиком множество $A$), мы можем не беспокоиться, поскольку первое по порядку невыброшенное слово принадлежит $A$. Как только все слова из $A$ будут выброшены, придётся заменить $A$, взяв в качестве нового кандидата первые $2^t$ невыброшенных (на данный момент) слов нужной длины. После этого мы спокойно ждём до тех пор, пока все слова нового множества $A$ не будут выброшены (не попадут в объединение множеств из всех $j$-списков для всех $j$); когда и если это случится, мы заменим $A$, взяв первые $2^t$ пока ещё не выброшенных слов, и так далее.

Рано или поздно этот процесс выбрасывания остановится, и текущее значение множества $A$ на этот момент будет содержать наше слово $x$. Таким образом, мы нашли множество правильного размера, содержащее $x$, но какова сложность этого множества?

Чтобы описать процесс порождения выбрасываемых множеств, достаточно знать последовательность $t_0, \dots, t_k$ (и длину слов, равную примерно $n$), то есть всего $m + O(\log n)$ битов информации. Поэтому с интересующей нас точностью сложность каждого из кандидатов на роль множества $A$ оценивается логарифмом его порядкового номера (сколько кандидатов перед ним пришлось отбросить). Таким образом, нам осталось доказать, что число отброшенных кандидатов ненамного больше $2^i$; тогда сложность любого из кандидатов (в том числе и последнего, правильного) будет ненамного больше $i$.

Итак, сколько раз мы могли заменять множество $A$ в связи с появлением новых множеств в списках? Отдельно посмотрим на появление множеств небольшой сложности и большого размера, а именно, входящих в $j$-списки с $j \le i$. Такое событие могло случиться не более $O(2^i)$ раз, так как в $j$-списке не более $O(2^i)$ множеств. Поэтому мы можем считать лишь интервалы между двумя соседними изменениями
ми множества А, в течение которых таких событий не случалось. Это значит, что все элементы предыдущего А были покрыты множествами из j-списков при j > i. Во всех этих множествах не так много элементов: общее количество слов во всех множествах j-списка не больше $2^i \cdot 2^j$; поскольку $t_j + j \le t_i + i$ и количество разных значений j невелико, получается всего примерно $O(2^{t_i+j})$ элементов, и после деления на $|A| = 2^i$ остаётся $2^i$ интервалов. ►

Эта теорема показывает, что, помимо сложности $KS(x)$, слово x может иметь другие «сложные характеристики»; такой характеристикой можно считать границу множества $P_x$ (или, если угодно, само множество). Эта характеристика, если можно так выразиться, «бесконечномерна» (представляет собой не одно число и не набор из двух, трёх или скольких-то чисел, а целую кривую).

**350** Докажите, что в теореме 253 нельзя потребовать, чтобы множество $P_x$ отстояло от T на расстояние $O(\log n)$ (а не на $O(\log n) + O(m)$). [Указание. Слов длины $n + O(\log n)$ существенно меньше, чем множеств T, удовлетворяющих условию теоремы.]

**351** Докажите, что не существует алгоритма, который по всякому данному слову х находил границу множества $P_x$ с точностью $O(\log I(x))$.

Более сильные результаты о невычислимости функции границы множества $P_x$ по х имеются в работе [177].

Классификацию слов по сложности можно представлять себе как вложенную цепочку множеств $S_0 \subset S_1 \subset S_2 \subset \dots$, где $S_i$ — множество слов сложности меньше i. В этой цепочке множества $S_i$ перечислимы равномерно по i и содержат $O(2^i)$ элементов.

Теперь вместо этой классификации у нас есть двумерная классификация множеств $S_{i,j}$, где множество $S_{i,j}$ состоит из всех слов x, входящих в конечные множества A с $KS(A) < i$ и $\log|A| < j$. (Такое множество A мы будем называть $(i * j)$-описанием любого его элемента x.) Мы получаем двумерную таблицу из множеств $S_{i,j}$, монотонную по обоим направлениям ($S_{i,j}$ растёт с ростом i и с ростом j). Кроме того, теорема 252 показывает, что эта таблица монотонна по диагонали: $S_{i,j} \subset S_{i+k,j-k}$. (Как всегда, мы пренебрегаем логарифмическими поправками: точнее следовало бы написать $S_{i,j} \subset S_{i+k+O(\log k),j-k}$.)

Чтобы лучше понять смысл этой двумерной «стратификации», полезно посмотреть на эквивалентные определения множеств $S_{i,j}$. При этом мы будем, как обычно, пренебрегать логарифмическими слагаемыми и считать два варианта определения (обозначаемые $S$ и $S'$) эквивалентными, если $S_{i,j} \subset S'_{i+O(\log n),j+O(\log n)}$ и наоборот (здесь и далее $n = i + j$).

Говоря о «перечне» в формулировке следующей теоремы, мы подразумеваем алгоритм, который работает и время от времени выдаёт на выход некоторые двоичные слова (возможно, с повторениями); длиной перечня мы будем называть общее число выданных слов (с учётом кратностей). В условии (в) мы считаем, что алгоритм может выдавать на выход слова не пододиночке, а «порциями» произвольного размера (который может меняться от порции к порции).
**Теорема 254.** Следующие свойства слова х эквивалентны в описанном смысле (из одного следует другое с логарифмической добавкой к параметрам):

(а) слово х принадлежит $S_{i,j}$ (имеет $(i * j)$-описание);

(б) существует простой (сложности $O(\log n)$) перечень длины не более $2^{i+j}$, в котором слово х в первый раз появляется за $2^j$ или более шагов от конца;

(в) существует простой (сложности $O(\log n)$) перечень длины не более $2^{i+j}$, включающий в себя х, в котором слова выдаются не более чем в $2^i$ порций;

(г) в любом простом (сложности $O(\log n)$) перечне, включающем все слова сложности не более $i+j$, слово х встречается за $2^j$ или более шагов от конца.

◀ Пусть выполнено (а). Будем перечислять все множества сложности не более $i$ и размера не более $2^j$. Когда очередное множество появляется, добавляем в перечень все его элементы. При этом получится не более чем $2^i$ порций с $2^j$ (или меньше) элементов в каждой, так что всего будет не более чем $2^{i+j}$ элементов, как и требуется в условии (в). При этом сложность перечня логарифмическая, так как нужно знать лишь $i$ и $j$. Итак, (а) ⇒ (б).

Чтобы получить (б), надо немного модифицировать конструкцию и добавлять после каждой порции $2^j$ произвольных ещё не порождённых элементов; общее число элементов увеличится на $2^{i+j}$, что в пределах допустимого. Таким образом, (а) ⇒ (б).

Напротив, из (б) легко следует (а), достаточно лишь нарезать элементы перечня на части размера $2^j$; при этом получится не более чем $2^i$ частей и останутся ненарезанными не более чем $2^j$ элементов. Следовательно, х войдёт в одну из частей. Каждая часть задаётся своим порядковым номером и потому имеет сложность $i$ (плюс логарифмическая добавка, включающая в себя сложность перечня).

Чтобы получить (а) из (в), при появлении каждой новой порции элементов перечня мы разбиваем её на части из $2^j$ элементов или меньше (для последней, неполной, части в каждой порции). Количество полных частей не превосходит $2^i$, поскольку длина перечня не превосходит $2^{i+j}$. Поэтому сложность каждой полной части не больше $i$ (описываем каждую полную часть её номером в порядке, задаваемым перечнем). Количество неполных частей также не больше $2^i$, поэтому сложность каждой из них также не больше $i$.

Итак, свойства (а) – (в) равносильны (с логарифмической точностью), и осталось показать, что они равносильны (г). Очевидно, что (г) является усилением (б), так что достаточно проверить, что из (а) следует (г).

Итак, пусть слово х содержится в некотором конечном множестве А сложности не более $i$, причём $\log|A| \le j$. Все элементы множества А, в том числе и х, имеют сложность не более $i + j + O(\log(i + j))$; пренебрегая логарифмическими поправками, мы будем опускать последнее слагаемое (надеясь, что привыкший к этому читатель легко внесёт необходимые исправления).

Пусть также дан некоторый простой перечень, включающий в себя все слова сложности не более $i+j$. Мы хотим доказать, что слово х появится в этом перечне не слишком поздно (после него будут ещё как минимум $2^j$ слов). Зная множество А, мы можем порождать перечень, пока в нём не обнаружатся все элементы А. Порождённая к этому моменту часть перечня представляет собой конечное множество В
сложности не более *i* (поскольку для задания *B* достаточно знать *A* и сам перечень, который прост). Рассмотрим первые (по порядку) 2<sup>j</sup> слов вне *B*: они определяются множеством *B* (*i* битов) и своим порядковым номером (*j* битов) и потому имеют сложность не более *i* + *j*; это и будут искомые 2<sup>j</sup> элементов перечня, стоящие в нём после *x*. ►

Можно сказать, что мы ввели дополнительную классификацию слов сложности не больше *n*, измеряя логарифм расстояния до конца списка таких слов. С точки зрения двумерной таблицы $S_{i,j}$ это соответствует возрастающей последовательности множеств $S_{i,j}$ на диагонали $i + j = n$ (строго говоря, возрастание множеств вдоль этой диагонали — при увеличении *i* и соответствующем уменьшении *j* — имеет место лишь с точностью до логарифмических поправок). Случайные слова длины $l \le n - O(\log n)$ (то есть слова сложности $l$ и длины $l$) стоят в начале этой классификации, имея $(n * 0)$-описания; в конце её стоят (немногочисленные) слова, имеющие лишь $(0 * n)$-описания.

**352** Показите, что все слова сложности *n*, стоящие в самом конце списка (с логарифмической точностью, то есть слова, за которыми стоит poly(*n*) слов), «почти одинаковы»: они имеют условную сложность $O(\log n)$ друг относительно друга.

Показите, что среди них находятся $B(n - c \log n)$ и $BB(n - c \log n)$, рассмотренные в разделе 1.2 (с. 32 и 34), для любых положительных *c* и *n*.

Если угодно, можно считать *n* минус логарифм расстояния до конца списка слов сложности не выше *n* мерой «извращённости» слова: случайные слова длины не более $n - O(\log n)$ при этом имеют нулевую извращённость, а слова у конца списка — максимальную (близкую к *n*). Но надо иметь в виду два важных обстоятельства.

* «извращённость» слов х и у может сильно отличаться, если даже $KS(x|y) \approx 0$ и $KS(y|x) \approx 0$. (В самом деле, кратчайшее описание у любого слова х является случайным и находится в самом начале соответствующего списка.) Однако если слова х и у переходят друг в друга при простой вычислимой биекции, это уже не так (см. следующую задачу).

* «извращённость» данного слова х сложности *n* (определяемая его местом в перечне всех слов сложности не выше *n*) может сильно упасть, если мы рассмотрим то же слово х в перечне слов сложности не больше $n'$ при $n' > n$. Так что фактически характеристикой слова х является функция $n' \mapsto$ расстояние от х до конца перечня слов сложности не выше $n'$. По существу это та же самая граничная кривая множества $P_x$, но только в других координатах (теперь мы смотрим на точки, в которых диагонали $i + j = n'$ заходят в множество $P_x$).

**353** Пусть слова х и у соответствуют друг другу при вычислимой биекции сложности *t*. Докажите, что если $x \in S_{i,j}$, то $y \in S_{i+O(t),j}$.

Напомним, что простая вычислимая биекция, переводящая одно слово в другое, существует, когда тотальная сложность любого из слов относительно второго мала (задача 31 на с. 45).
Возвращаясь к теореме 15 (с. 36), можно сказать, что эта теорема выделяла среди слов сложности $n$ некоторые особые слова (все имеющие малую сложность относительно друг друга). Теперь мы можем объяснить смысл этой «особой точки» ещё одним способом: это слова, стоящие у конца списка и эквивалентные им слова. Среди эквивалентных, отметим, есть и стохастические, длина которых близка к сложности. Такова, например, двоичная запись числа $k_n$ слов сложности не больше $n$ (пункт (б) в теореме 15) или числа $m_n$ слов длины не более $n$, на которых определён оптимальный декомпрессор.

Кстати, использованное при доказательстве теоремы 254 рассуждение позволяет установить связь между $k_n$ (или $m_n$) при разных $n$, как показывает следующая задача:

**354** Докажите, что при $n' < n$ слово $k_{n'}$ (точнее следовало бы сказать «слово, являющееся двоичной записью числа $k_{n'}$» эквивалентно (с точностью до условной сложности $O(\log n)$) первым $n'$ битам слова $k_n$. Докажите аналогичное утверждение для слов $m_n$ и $m_{n'}$. [Указание. Для $k_n$ по существу надо доказать, что указание списка слов сложности не больше $n$ с не более чем $2^s$ пропусками равносильно указанию числа, большего $B(n-s)$. В одну сторону: зная такой список, мы依赖аемся $T$ шагов, пока в перечислении слов сложности не больше $n$ появятся все элементы этого списка. Любое число $t > T$ должно иметь сложность не меньше $n-s$, иначе по этому числу можно было построить список сложности меньше $n-s$, содержащий все слова сложности $n$, кроме $2^s$, и первые $2^s$ слов вне этого списка приводили бы к противоречию. В другую сторону: будем перечислять слова сложности не больше $n$, выдавая их порциями по $2^s$ штук; зная $B(n-s)$, можно найти число полных порций (шаг, на котором появляется последняя полная порция, не превосходит $B(n-s)$, поскольку определяется числом полных порций и имеет сложность не больше $n-s$) и тем самым получить искомый список с точностью до последней неполной порции. Аналогичное рассуждение годится и для $m_n$.]

Следующий результат обобщает утверждение задачи 39 (с. 50). Там по существу утверждалось, что если слово $x$ имеет много описаний данной длины, то оно имеет и описания меньшей длины. Оказывается, что аналогичное утверждение верно и для $(i \ast j)$-описаний.

**Теорема 255.** Пусть для слова $x$ существует не менее $2^k$ множеств, являющихся его $(i \ast j)$-описаниями. Тогда оно имеет $(i \ast (j-k))$-описание и даже $((i-k) \ast j)$-описание.

В формулировке этой теоремы мы, как и раньше, опускаем слагаемые вида $O(\log(i+j+k))$, которые разрешается прибавлять к параметрам описаний. Слово «даже» напоминает о теореме 252, которая позволяет от $(i-k) \ast j$ перейти к $i \ast (j-k)$.

◀ Первое (более простое) утверждение теоремы легко следует из рассуждений, использованных в доказательстве теоремы 254. Будем перечислять все множества А сложности не более $i$ и размера не более $2^j$ и смотреть, какие элементы $x$ покрыты ими с кратностью $2^k$. Таких элементов будет не более $2^{i+j}/2^k = 2^{i+j-k}$, и они выдаются не более чем в $2^i$ порций (каждое новое множество А соответствует одной порции). Остаётся вспомнить свойство (в) теоремы 254.
Для доказательства второго утверждения нам понадобится уменьшить число порций до $2^{i-k}$. Вот как это делается. По-прежнему перечисляя множества сложности не более *i* и размера не более $2^j$, мы теперь обращаем внимание не только на «полноценные» элементы, покрытые с кратностью $2^k$, но и на «кандидатов» — элементы, покрытые с двоее меньшей кратностью $(2^{k-1})$. Как только появляется полноценный элемент, не вошедший в перечень, мы включаем в этот перечень не только его, но заодно уж и всех обнаруженных к этому моменту кандидатов (кроме уже включённых в перечень). От этого общее число включённых в перечень элементов увеличится не более чем двое (что несущественно при нашей логарифмической точности). Зато число порций сильно уменьшится: ведь каждая из них включает в перечень всех кандидатов, и чтобы появился непокрытый полноценный элемент, нужно не менее $2^{k-1}$ новых множеств (кратность должна возрасти по меньшей мере от $2^{k-1}$ до $2^k$). Это и даёт необходимое уменьшение числа порций. ►

Только что доказанную теорему можно переформулировать следующим образом:

**Теорема 256.** Если слово х имеет $(i \ast j)$-описание А, для которого выполнено неравенство $KS(A|x) \ge k$, то оно имеет и $(i \ast (j - k))$-описание и даже $((i - k) \ast j)$-описание.

(Как и раньше, мы опускаем логарифмические слагаемые, необходимые в точной формулировке.)

◀ В самом деле, зная слово х, а также значения параметров *i* и *j* (последнее требует логарифмического числа битов), мы можем перечислять все $(i \ast j)$-описания слова х. Поэтому сложность таких описаний (с точностью до логарифмических слагаемых) не превосходит их числа. Если есть описание А с большим $KS(A|x)$, то описаний много и можно применить предыдущую теорему. ►

Эта теорема гарантирует, что если мы берём описания с предельно возможными параметрами (на границе множества $P_x$ для данного х), то все эти описания будут просты относительно х. Что, с точки зрения здравого смысла, довольно естественно: если в описании есть «лишняя» (не входящая в х) информация, то вряд ли оно будет оптимальным.

## 14.4. Ограниченные классы гипотез

В этом разделе мы будем предполагать, что в качестве статистических гипотез разрешены только множества из некоторого семейства множеств $\mathcal{A}$. Ограничение класса гипотез означает, что у нас заранее имеется некоторая информация об источнике происхождения данного слова х. А именно, нам известно, что слово х было получено случайным выбором в одном из множеств из $\mathcal{A}$ (но мы не знаем, в каком). Поэтому, подыскивая статистическую гипотезу для х, мы ограничиваемся множествами, принадлежащими $\mathcal{A}$.

Оказывается, основные результаты предыдущих параграфов обобщаются (с небокрытым ухудшением оценок) на случай любых семейств $\mathcal{A}$, удовлетворяет следующим трем условиям.
(1) Семейство $\mathcal{A}$ перечислимо. Это означает, что имеется алгоритм, печатающий в некотором порядке списки элементов всех множеств из $\mathcal{A}$; список очередного множества можно начинать только тогда, когда уже закончен список предыдущего.

(2) Для всех $n$ семейство $\mathcal{A}$ содержит множество всех слов длины $n$.

(3) Для некоторого полинома $p$, для каждого множества $A \in \mathcal{A}$ и для любых натуральных чисел $n$ и $c < |A|$ выполнено следующее: существует покрытие множества всех слов длины $n$ из $A$ не более чем $p(n)|A|/c$ множествами из $\mathcal{A}$, причем мощность каждого из покрывающих множеств не превосходит $c$.

Поясним смысл последнего условия. Теорема 252 утверждает, что если слово имеет $(i * j)$-описание, то оно имеет и $((i + k) * (j - k))$-описание (для всякого $k \le j$). В доказательстве этой теоремы мы разбивали данное $(i * j)$-описание на $2^k$ частей, каждая размером не больше $2^{j-k}$. Третье условие гарантирует возможность такого разбиения, правда, на немного большее количество кусков (в полиномиальное от $n$ количество раз).

Пусть дано слово $x$. По аналогии с множеством $P_x$, определённым на с. 476, обозначим через $P_x^\mathcal{A}$ множество пар $\langle i, j \rangle$, для которых $x$ имеет $(i * j)$-описание, принадлежащее семейству $\mathcal{A}$. Если семейство $\mathcal{A}$ состоит из всех конечных подмножеств, то никаких ограничений нет, и тем самым $P_x^\mathcal{A} = P_x$. Для ограниченных семейств множество $P_x^\mathcal{A}$ всегда включено в множество $P_x$ и чем меньше семейство $\mathcal{A}$, тем меньше множество $P_x^\mathcal{A}$.

Условия (1)–(3) гарантируют, что множества $P_x^\mathcal{A}$ обладают теми же свойствами, что и множества $P_x$. А именно, для любого слова длины $n$ выполнено следующее:

* Множество $P_x^\mathcal{A}$ содержит пару, отстоящую от пары $\langle 0, n \rangle$ не более, чем на $O(\log n)$. Действительно, по свойству (2) семейство $\mathcal{A}$ содержит множество всех слов длины $n$, а значит любое слово длины $n$ имеет $0 * n$-описание в $\mathcal{A}$ (игнорируя логарифмические добавки).

* Множество $P_x^\mathcal{A}$ содержит пару, отстоящую от пары $\langle KS(x), 0 \rangle$ не более чем на константу. Действительно, из условия (3), примененного к $c=1$ и множеству всех слов длины $n$ в качестве $A$, следует, что $\mathcal{A}$ содержит все синглетоны, поэтому каждое слово имеет $(KS(x) * 0)$-описание (с точностью до $O(1)$-добавок).

* Имеет место аналог теоремы 252: если $x$ имеет $(i * j)$-описание в $\mathcal{A}$, то для всех $k \le j$ оно имеет и $((i + k) * (j - k))$-описание в $\mathcal{A}$. (В аккуратной формулировке к $i + k$ надо добавить еще $O(\log l(x))$.) Действительно, пусть $x$ имеет $(i * j)$-описание $A \in \mathcal{A}$. Пусть нам дано $n = l(x)$, множество $A$ и $k$. Будем порождать множества из семейства $\mathcal{A}$ до тех пор, пока не найдем покрытие множества всех слов длины $n$ из $A$ не более чем $p(n)2^k$ множествами мощности $|A|2^{-k}$ или менее (здесь $p$ — полином из условия (3)). Сложность множества, покрывающего $x$, не превосходит $i + k + O(\log n + \log k)$, поскольку его можно найти, зная $A$, $n$, $k$ и его порядковый номер среди множеств, покрывающих $A$. Без ограничения общности мы можем считать, что $k \le n$, поскольку иначе утверждение очевидно — искомым описанием является синглетон $\{x\}$. Поэтому слагаемое $O(\log k)$ можно опустить.
Пример. Пусть семейство $\mathcal{A}$ состоит из всех шаров Хемминга, то есть множеств вида $\{x | l(x) = l(y), d(x,y) \le r\}$, где у — некоторое слово (называемое центром шара), $r$ — некоторое натуральное число, называемое радиусом шара, а $d(x,y)$ обозначает расстояние Хемминга (количество позиций, в которых $x$ и $y$ различны). Неформально говоря, нам известно, что для некоторого слова $y$ и некоторого натурального $r$ слово $x$ было получено из $y$ изменением не более чем $r$ битов, при этом номера измененных битов выбирались случайно. Сами $y$ и $r$ при этом неизвестны. Например, слово $y$ было передано нам по ненадежному каналу связи и полученное нами вместо $y$ слово $x$ отличается от $y$ в небольшом количестве позиций.

**355** Докажите, что для любого $r \le n$ множество всех слов длины $n$ можно покрыть $\text{poly}(n)2^n/V$ шарами Хемминга радиуса $r$, где $V$ обозначает мощность шара радиуса $r$. [Указание. Выберем случайным образом $N$ шаров радиуса $r$. Для фиксированного слова $x$ вероятность того, что оно не будет покрыто ни одним из выбранных шаров равна $(1 - V^{2-n})^N < e^{-V^{2-n}}$. Если положить $N = n \ln 2 \cdot 2^n / V$, то эта верхняя оценка будет равна $2^{-n}$. Значит при таком $N$ вероятность того, что хотя бы одно слово длины $n$ не будет покрыто, меньше 1.]

**356** Докажите, что семейство всех шаров Хемминга удовлетворяет условиям (1)-(3). [Указание. Пусть дан шар $A$ радиуса $a$ и число $c < |A|$. Нам нужно покрыть $A$ шарамами мощности $c$ или меньше. Поскольку множество всех слов длины $n$ можно покрыть двумя шарами радиуса $n/2$, без ограничения общности мы можем считать, что $a \le n/2$. Выберем наибольшее $b \le n/2$ такое, что мощность $|B|$ шара радиуса $b$ не превосходит $c$, и будем искать покрытие $A$ шарами радиуса $b$. Мощности шаров Хемминга с радиусами, различающимися на 1, отличаются не более, чем в $n+1$ раз, поэтому $|B| \ge c/(n+1)$ и нам достаточно покрыть $A$ не более чем $\text{poly}(n)|A|/|B|$ шарами радиуса $b$.

Покроем все точки на расстоянии не более $b$ от центра шара $A$ одним шаром радиуса $b$ (с тем же центром). Остаток шара разобьем на концентрические сферы: каждая сфера состоит из всех точек на расстоянии ровно $d$ от центра шара $A$, где $d \in \{b+1, b+2, \dots, a\}$. Количество сфер не превосходит $n$, поэтому достаточно научиться покрывать сферу $S$ радиуса $d \in (b, n/2]$ не более чем $\text{poly}(n)|S|/|B|$ шарами радиуса $b$.

Для этого в качестве $f$ возьмём решение уравнения $b + f(1 - 2b/n) = d$, округлённое до ближайшего целого числа. Выберем случайным образом шар $B$ радиуса $b$ с центром на расстоянии $f$ от центра $S$. Не менее $1/\text{poly}(n)$-й части точек любого такого шара $B$ принадлежат $S$. Действительно, обозначим через $x$ и $y$ центры $S$ и $B$, соответственно. Выберем в слове $y$ некоторую $(b/n)$-ю часть битов, в которых $y$ совпадает с $x$, и некоторую $(b/n)$-ю часть битов, в которых $y$ отличается от $x$, и изменим все выбранные биты. Любое слово, полученное таким образом, расположено на расстоянии $b$ от $y$ и на расстоянии $f - (b/n)f + (n-f)(b/n) = d$ от $x$. Общее количество таких слов равно $C_f^{f(b/n)} C_{n-f}^{(n-f)(b/n)}$, что с точностью до умножения на полином от $n$ равно

$$2^{fh(b/n, 1-b/n)} + (n-f)h(b/n, 1-b/n) = 2^{nh(b/n, 1-b/n)}.$$
Мощность $|B|$ шара радиуса $b$ также равна этому числу (с той же точностью). Итак, каждый шар $B$ радиуса $h$ с центром на расстоянии $f$ от $x$ покрывает не менее $|B|/\text{poly}(n)$ точек из $S$. При случайном выборе шара $B$ каждое $z \in S$ имеет равные шансы быть покрытым. Поэтому вероятность того, что любое фиксированное $z \in S$ покрывается случайным шаром $B$, не меньше $|B|/(|S|\text{poly}(n))$. Следовательно, для подходящего полинома с большой вероятностью случайно выбранные $\text{poly}(n)|S|/|B|$ шаров радиуса $b$ с центром на расстоянии $f$ от $x$ покрют все точки $S$.

**357** Пусть семейство $\mathcal{A}$ состоит из всех шаров Хемминга. Докажите, что существуют такие слова $x$, для которых множество $P_x^{\mathcal{A}}$ значительно меньше множества $P_x$: для некоторого положительного $\epsilon$ для всех достаточно больших $n$ существует слово $x$ длины $n$, для которого $P_x^{\mathcal{A}}$ отстоит от $P_x$ более чем на $\epsilon n$. [Указание. Фиксируем любое $0 < \alpha < 1/2$ и обозначим через $V$ мощность шара радиуса $\alpha n$. Для данного $n$ найдём перебором некоторое множество $E$, состоящее из $N = 2^n/V$ слов длины $n$, для которого шар Хемминга радиуса $\alpha n$ содержит не более $n$ слов из $E$. (Существование такого множества можно доказать вероятностными рассуждениями: если выбрать случайно $N$ слов длины $n$, то они с положительной вероятностью образуют нужное множество.) Возьмем в качестве $x$ случайное слово из $E$, то есть, любое слово $x$ в $E$ сложности примерно $\log|E| = n - \log V$. Сложность любого шара $A$ радиуса $\alpha n$, содержащего $x$, не меньше $KS(x) = n - \log V$ (с точностью $O(\log n)$). В самом деле, зная шар $A$ и номер $x$ в $A \cap E$, можно найти $x$. Поэтому точка $(n - \log V, \log V)$ находится в логарифмической окрестности границы множества $P_x^{\mathcal{A}}$. С другой стороны, граница множества $P_x$ находится ниже прямой $KS(A) + \log|A| = n - \log V$. Это следует из того, что $x$ имеет $(0*(n - \log V))$-описание (с логарифмической точностью) — это само множество $E$.]

**358** Опишите множество $P_x^{\mathcal{A}}$ для $x$ и $\mathcal{A}$ из предыдущей задачи. [Указание. Граница множества $P_x^{\mathcal{A}}$ состоит из вертикального отрезка $KS(A) = n - \log V$, $\log|A| \le \log V$ и отрезка $KS(A) + \log|A| = n$, $\log V \le \log|A|$, наклонённого под углом в $45^\circ$ к осям координат.]

Пусть семейство $\mathcal{A}$ обладает свойствами (1)–(3). Тогда выполнен аналог теоремы 253 с немного худшей точностью: $O(\log n)$ надо заменить на $O(\sqrt{n \log n})$.

**Теорема 257.** Пусть $k \le n$ и пусть $n = t_0 > t_1 > \dots > t_k = 0$ — последовательность натуральных чисел, имеющая сложность $m$. Тогда существует слово $x$ сложности $k + O(\sqrt{n \log n}) + O(m)$ и длины $n + O(\log n)$, для которого множество $P_x^{\mathcal{A}}$ отстоит от множества $T = \{\langle i, j \rangle \mid (i \le k) \Rightarrow (j \ge t_i)\}$ не более чем на $O(\sqrt{n \log n}) + O(m)$.

◀ Доказательство похоже на доказательство теоремы 253. Вспомним, как проходило то доказательство. В качестве $x$ мы брали первое в словарном порядке слово подходящей длины $n'$, которое не принадлежит ни одному множеству сложности меньше $i$ и мощности не больше $2^i$, если точки $(i, j)$ брать на границе множества $T$ (будем называть такие множества «плохими»). Длина $n'$ выбиралась так, чтобы общее количество слов в плохих множествах было строго меньше количества слов длины $n'$. Кроме того, для каждой из граничных точек $(i, j)$ мы строили
множество $A_{ij}$, содержащее х, имеющее мощность $2^j$ и сложность, близкую к i. Множества $A_{ij}$ строились «с нескольких попыток». А именно, сначала для каждого j мы заносили в $A_{ij}$ первые в словарном порядке $2^j$ слов. Затем мы запускали процесс перечисления плохих множеств и выбрасывали из всех $A_{ij}$ элементы всех обнаруженных плохих множеств. Как только в результате выбрасывания некоторое множество $A_{ij}$ опустевало, мы заполняли его первыми в словарном порядке $2^j$ неброшенными словами. Этим мы гарантировали, что в любой момент каждое из $A_{ij}$ содержит первое в словарном порядке невыброшенное слово. В частности, это верно и после того, как обнаружены все плохие множества и изменение множеств $A_{ij}$ прекратилось. Поэтому после стабилизации каждое из множеств $A_{ij}$ содержит выбранное нами слово х. Каждое $A_{ij}$ можно задать порядковым номером его последнего изменения плюс небольшой объем информации, нужный, чтобы задать j и опустить процесс перечисления плохих множеств. Поэтому нам было достаточно доказать, что логарифм количества изменений $A_{ij}$ лишь ненамного превосходит i. Это следовало из того, что после каждого опустения множество $A_{ij}$ заполнялось заново до нужной мощности. Чтобы опустошить его еще раз, нужно либо появление достаточного количества новых мелких плохих множеств (мощности меньше $2^j$), либо появление одного нового крупного (мощности больше $2^j$). Из формы границы T следовало, что общее количество элементов в мелких плохих множествах не больше $2^{i+j}$ (с точностью до полиномиального от n множителя), поэтому они могут опустошать множество $A_{ij}$ не более $2^i$ раз. А количество крупных плохих множеств не превосходит $2^i$, поскольку сложность каждого из них меньше i. (Точнее следует сказать, что количество интервалов между соседними изменениями множества $A_{ij}$, во время которых не появлялось крупных множеств, не больше $2^i$.)

Почему это доказательство, как есть, не переносится на произвольное семейство множеств $\mathcal{A}$? Мы по-прежнему можем порождать плохие множества из нашего семейства, и общее количество элементов в них ограничено той же формулой, поэтому мы можем выбрать ту же длину $n'$ ишкомого слова х. Причём перечисливость $\mathcal{A}$ нам даже не нужна — не будет никакой беды, если мы учтём и плохие множества вне $\mathcal{A}$. Проблема в том, что теперь мы не можем наполнить опустевшее $A_{ij}$ первыми $2^j$ невыброшенными словами — полученное множество может не принадлежать семейству $\mathcal{A}$. Из-за этого мы не можем выбрать слово х заранее. Теперь х будет определяться не только множеством слов, входящих в объединение плохих множеств, но и порядком их появления. Нам придётся, наблюдая за их появлением, строить «хорошие» множества $A_{ij}$ с непустым пересечением так, чтобы каждое из них изменялось не слишком много раз.<fnref n="1" /> Для последнего важно, чтобы мощность пересечения хороших крупных множеств (мощности не менее $2^j$) была близка к $2^j$. В этом случае можно будет использовать те же рассуждения, что и раньше. В самом деле, чтобы это пересечение стало пустым, должно появиться много плохих мелких множеств или одно плохое крупное, поэтому пересечение будет редко опустевать, а значит, крупные множества будут меняться редко.

<footnote n="1">¹Раньше непустота пересечения хороших множеств гарантировалась непустотой каждого из них — теперь так не получится.</footnote>
При построении хороших множеств мы будем использовать следующий алгоритм. Допустим, имеются некоторые хорошие множества $A_1, \dots, A_l$, причём наименьшее из них $A_l$ имеет мощность не более $2^l$, а их пересечение содержит не менее $\beta 2^j$ невыброшенных слов. Мы хотим добавить к ним еще одно хорошее множество $A_{l+1}$ мощности не более $2^s < 2^j$ таким образом, чтобы пересечение $A_1, \dots, A_{l+1}$ содержало побольше невыброшенных слов. Для этого мы покрываем $A_l$ не более чем $\text{poly}(n')2^{j-s}$ множествами из $\mathcal{A}$, мощности не более $2^s$ каждое, и выбираем среди них то, которое покрывает наибольшее количество невыброшенных слов из пересечения $A_1 \cap \dots \cap A_l$. Возможность такого покрытия обеспечивается третьим из принятых требований к семейству $\mathcal{A}$, и его можно найти алгоритмически — это обеспечивается первым требованием к семейству. При таком алгоритме выбора $A_{l+1}$ пересечение $A_1, \dots, A_{l+1}$ содержит не менее

$$ \frac{\beta 2^j}{\text{poly}(n')2^{j-s}} = \frac{\beta 2^s}{\text{poly}(n')} $$

невыброшенных слов.

Чтобы построить семейство хороших множеств, содержащее по одному множеству $A_{it_i}$ для каждой точки $(i, t_i)$ на границе $T$, нужно применить эту процедуру $k$ раз. При каждом применении параметр $\beta$ уменьшается в $\alpha = \text{poly}(n')$ раз. Таким образом, мы можем гарантировать лишь, что размер пересечения первых $i$ множеств не меньше $\alpha^{-i} 2^{t_i}$. При большей $i$ это во много раз меньше необходимого $2^{t_i}$. Поэтому с помощью этого алгоритма (а другого у нас нет) не построить семейство хороших множеств, содержащее по одному множеству $A_{ij}$ для каждой точки $(i, j)$ на границе $T$ (с соблюдением требования о мощности пересечений). Значит нам придётся рассматривать не все точки на границе, а только небольшую их часть.

Выберем $N = \sqrt{n/\log n}$ точек на границе $T$, идущих через равные интервалы по второй координате, начиная с точки $(0, n)$ и заканчивая точкой $(k, 0)$. А затем докажем, что найдётся $x$, для которого для каждой выбранной точки $(i, j)$ наименьшая сложность множества из $\mathcal{A}$ размера $2^j$ (или меньше) близка к $i$. Почему этого достаточно? При выбранном нами $N$ вторые координаты соседних выбранных точек отличаются на $\sqrt{n \log n}$. Поскольку граница $T$ спускается под углом в $45^\circ$ или более, разность первых компонент соседних выбранных граничных точек не больше разности их вторых компонент (а значит, не больше $\sqrt{n \log n}$). В частности, у выбранных точек при росте второй координаты сумма $i+j$ не возрастает (это нам понадобится в дальнейшем). Граница множества $T$ монотонна, поэтому все её точки между любыми соседними выбранными точками близки к выбранным точкам (отстоят от них не более чем на $\sqrt{n \log n}$). То же самое верно и для границы множества $P_x^\mathcal{A}$: между соседними горизонталями (из выбранных) все её точки близки к крайним. А крайние точки по построению близки к границе $T$. Поэтому границы множеств $T$ и $P_x^\mathcal{A}$ будут близки, следовательно, и сами множества будут близки.

Теперь перейдём к построению $x$ и хороших множеств. У нас имеется $N$ выбранных граничных точек $(i, j)$, которые мы будем нумеровать $i_1, j_1$ в порядке убывлания второй координаты, так что $j_1 = n$ и $j_N = 0$. Сначала для каждого $l$ в порядке возрастания найдём «хорошее» множество $A_l$ из $\mathcal{A}$ мощности не более $2^l$ таким
образом, чтобы мощность пересечения первых $l$ хороших множеств была не меньше $\alpha^{-l} 2^{n'_{l}}$. Для этого мы $N$ раз применяем описанный выше алгоритм, взяв в качестве $A_0$ множество всех слов длины $n'$ (по условию оно принадлежит семейству $\mathcal{A}$).

Затем мы начинаем перечислять «плохие» множества. При появлении очередного плохого множества мы выбрасываем все его элементы из множества всех слов длины $n'$ (и из всех хороших множеств). Длину $n'$ выбираем так, чтобы общее количество выброшенных слов никогда не превзошло половины от $2^{n'}$ (ясно, что нам хватит $n' = n + O(\log n)$).

Как только в результате выбрасывания пересечение первых $l$ хороших множеств станет слишком маленьким для хотя бы одного $l \le N$, мы находим наименьшее такое $l$ и обновляем описанным выше алгоритмом все хорошие множества, начиная с $l$-го, в порядке возрастания номеров. (Нулевым хорошим множеством будем считать множество всех слов длины $n'$ и положим $l_0 = n'$..) Будем называть эту процедуру $l$-обновлением: при $l$-обновлении хорошие множества с номерами меньше $l$ не меняются, а все остальные обновляются.

Как выбрать порог для размера пересечения первых $l$ множеств, при достижении которого мы производим $l$-обновление? Его выбор должен обеспечивать верхнюю оценку $2^{n'_{l}}$ для числа $l$-обновлений. Для этого нужно, чтобы сразу после обновления $l$-го хорошего множества мощность пересечения первых $l$ множеств была существенно (скажем, вдвое) больше этого порога. Вспомним, что при обновлении $l$-го множества порог для $(l-1)$-го множества ещё не перейдён. Поэтому наш алгоритм гарантирует, что пересечение первых $l$ множеств имеет не меньше

$$v_{l-1}/\alpha 2^{n'_{l-1}-n'_{l}}$$

слов. Таким образом, нам достаточно, чтобы порог для $l$-го множества был, скажем, вдвое больше этой величины. Кроме того, нам нужно, чтобы порог $v_0$ для нулевого хорошего множества $A_0$ никогда не был перейден. Этим требованиям очевидно удовлетворяют числа

$$v_l = (2\alpha)^{-l} 2^{n'_{l}/2}.$$

При таком выборе порога после каждого $l$-обновления для всех изменённых хороших множеств $A_r$ мощность пересечения первых $r$ хороших множеств не меньше $2v_r$. Следовательно, между любыми двумя последовательными $l$-обновлениями должно быть выброшено не менее $v_l$ слов (более того, для любого $l$-обновления в интервале между последним $s$-обновлением для $s \le l$ перед ним и им самим должно быть выброшено не менее $v_l$ слов).

Убедимся, что это гарантирует желаемую верхнюю оценку для количества изменений $l$-го хорошего множества. Оно меняется только при $s$-обновлениях для $s \le l$. Между любыми двумя последовательными $s$-обновлениями должно быть выброшено не менее $v_s$ слов, что не меньше $v_l$. Выбрасывание $v_l$ слов может быть вызвано появлением нового «крупного» плохого множества (крупными мы называем множества мощности больше $2^{n'_{l}}$), либо порождением достаточного количества мелких плохих множеств (мощности не больше $2^{n'_{l}}$). Общее количество крупных множеств меньше $\sum_{r<l} 2^{n'_{r}}$, а общее количество слов в мелких множествах меньше
$\sum_{r \ge l} 2^{i_r + j_r}$. Поэтому общее количество s-обновлений для любого фиксированного $s \le l$ ограничено сверху величиной

$$ \sum_{r<l} 2^{i_r} + \sum_{r \ge l} \frac{2^{i_r + j_r}}{\nu_l}. $$

(Здесь первое слагаемое есть общее количество интервалов между последовательными s-обновлениями, во время которых появлялись крупные множества, а второе слагаемое есть общее количество интервалов между последовательными s-обновлениями, во время которых не появлялось крупных множеств.) В силу неубывания чисел $i_r$ первое слагаемое не превосходит $N2^{i_r}$. Числа $i_r + j_r$ не возрастают с ростом $r$, поэтому второе слагаемое не больше $N2^{i_r+j_r}/\nu_l$. Вспомнив, что $\nu_l = (2\alpha)^{-l}2^{j_r-1}$ и $\alpha = \text{poly}(n')$, мы видим, что второе слагаемое не больше

$$ N2^{i_r+j_r+N\log 2\alpha-j_r+1} = N2^{i_r+O(N\log n')}. $$

Итак, количество s-обновлений для фиксированного $s \le l$ меньше

$$ N2^{i_r+O(N\log n')}, $$

следовательно, количество изменений $l$-го хорошего множества меньше

$$ N2^{i_r+O(N\log n')}. $$

Число $n'$ примерно равно $n$, а $N$ есть $\sqrt{n/\log n}$. Поэтому сложность $l$-го хорошего множества не больше $i_l + O(\sqrt{n\log n}) + O(m+\log n)$ (мы добавили сложность описания множества $T$ и $l$).

Когда новые плохие множества перестанут появляться, хорошие множества также перестанут изменяться. В качестве $x$ выберем единственное слово из пересечения всех хороших множеств (напомним, что среди них имеется синглетон), полученных к этому моменту. Сложность этого слова находится в нужных пределах, поскольку по построению наименьшая сложность синглетона, содержащего $x$, примерно равна $i_N = k$. ►

**Замечание.** В доказательстве мы выбрасывали слова из всех плохих множеств, а не только множеств из $\mathcal{A}$. Поэтому верхняя оценка множества $P_x^{\mathcal{A}}$ верна и для семейства, состоящего из всех конечных множеств. Иными словами, мы добились, что слово $x$ имеет заданное множество $P_x^{\mathcal{A}}$ не только для исходного $\mathcal{A}$, но и для всех семейств конечных множеств, включающих $\mathcal{A}$ (не обязательно удовлетворяющим трём условиям на с. 484).

**359** Проведите это рассуждение подробно.

**360** (a) Пусть $x$ — слово длины $n$, а $r$ — натуральное число, не превосходящее $n/2$. Обозначим через $KS_r(x)$ наименьшую (простую) сложность слова у той же длины, что $x$, отличающегося от $x$ не более чем в $r$ позициях. Доказательно, что $KS_r(x)$ с точностью до $O(\log n)$ равно наименьшему $i$, для которого $x$ имеет $(i * \log V(r))$-описание, являющееся шаром Хемминга, где $V(r)$ обозначает мощность шара Хемминга радиуса $r$.
(6) Опишите все возможные формы функции $r \mapsto KS_r(x)$ с точностью до слагаемого $O(\sqrt{n \log n})$. [Указание. Для всех слов $x$ длины $n$ выполнено $KS_0(x) = KS(x)$, $KS_n(x) = O(\log n)$ и

$$0 \le KS_a(x) - KS_b(x) \le \log(V(b)/V(a)) + O(\log n)$$

для всех $a < b \le n/2$. Обратно, для любых чисел $k \le n$ и для любой функции $t: \{0, 1, \dots, n\} \to \mathbb{N}$ сложности $m$, удовлетворяющей условиям $t(0) = k$, $t(n) = 0$ и $0 \le t(a) - t(b) \le \log(V(b)/\log V(a))$ для всех $a < b \le n/2$, существует слово $x$ длины $n$ и сложности $k + O(\sqrt{n \log n}) + O(m)$, для которого $KS_a(x) = t(a) + O(\sqrt{n \log n}) + O(m)$.

Сложность $KS_r(x)$ была впервые определена в работе [54]. В работе [42] изучены два варианта определения условной сложности с ошибками: равномерный и неравномерный варианты. Равномерная условная сложность с ошибками $KS_{rs}^u(x|y)$ определяется, как наименьшая сложность программы, которая по любому слову $y'$ на расстоянии не более $s$ от $y$ выдаёт некоторое слово $x'$ на расстоянии не более $r$ от $x$ (слово $x'$ может зависеть от $y'$). Неравномерная сложность с ошибками $KS_{rs}(x|y)$ определяется как $max_{y'} \min_x KS(x'|y')$, если рассматривать $x'$ не дальше $r$ от $x$, а $y'$ не дальше $s$ от $y$. В определении неравномерной сложности программа переработки $y'$ в $x'$ может зависеть от $y'$, а в определении равномерной сложности — не может. Поэтому неравномерная сложность меньше равномерной и может быть значительно меньше неё (последнего мы доказывать не будем, отсылая читателя к [42]).

Теорема 254 давала критерий того, что данное слово имеет $(i * j)$-описание (без ограничения класса описаний). Неясно, имеет ли она аналог для произвольного семейства множеств $\mathcal{A}$. Но утверждение следующей за ней теоремы 255 переносится почти без изменений на случай произвольного перечислимого семейства множеств.

**Теорема 258.** Пусть семейство $\mathcal{A}$ перечислимо. Пусть слово $x$ длины $n$ имеет не менее $2^k$ множеств из $\mathcal{A}$, являющихся его $(i * j)$-описаниями. Тогда оно имеет $((i - k) * j)$-описание в $\mathcal{A}$ (и, следовательно, $(i * (j - k))$-описание, если семейство $\mathcal{A}$ удовлетворяет условию (3) на с. 484).

В формулировке этой теоремы мы, как и раньше, опускаем слагаемые вида $O(\log(n + i + j + k))$, которые разрешается прибавлять к параметрам описаний.

◀ Пусть даны $i, j, n, k$. Будем перечислять все $(i * j)$-описания из $\mathcal{A}$, то есть множества мощности не более $2^j$ и сложности не более $i$, отбирая некоторые из них. При отборе мы стремимся обеспечить следующее: в любой момент каждое слово $x$ длины $n$, которое имеет не менее $2^k$ описаний (среди уже обнаруженных), принадлежит хотя бы одному из отобранных множеств, а общее количество отобранных множеств не превосходит $2^{i-k}p(n, k, i, j)$, где $p$ — некоторый полином. Нам достаточно доказать, что для некоторого полинома $p$ существует стратегия отбора, гарантирующая выполнение этих двух требований. (Поскольку стратегия может быть найдена перебором по данным $n, i, j, k$, ее колмогоровская сложность ограничена $O(\log(n + k + i + j))$.)

Существование такой стратегии можно доказать конструктивно и с помощью вероятностного рассуждения.
**Вероятностное доказательство.** Рассмотрим игру двух противников, в которой игроки ходят по очереди и каждый делает $2^i$ ходов. Первый игрок, совершая ход, указывает некоторое множество слов длины $n$, а второй на следующем за этим ходу сообщает, отбирает он это множество или нет. Второй игрок проигрывает, если после некоторого его хода количество отобранных множеств превысит

$$2^{i-k+1}(n+1)\ln 2$$

или найдется слово х длины $n$, принадлежащее не менее $2^k$ множествам первого игрока, но не принадлежащее ни одному из отобранных множеств.

В этой игре один из игроков имеет выигрышную стратегию. Мы утверждаем, что этим игроком является второй. Рассуждая от противного, допустим, что выигрышную стратегию имеет первый. Фиксируем такую стратегию и предполагаем, что первый игрок её придерживается.

Рассмотрим следующую вероятностную стратегию для второго игрока: после каждого хода А первого игрока отбираем множество А с вероятностью

$$p = 2^{-k}(n+1)\ln 2.$$

Чтобы получить противоречие, нам достаточно доказать, что эта стратегия выигрывает с положительной вероятностью.

Среднее количество отобранных множеств равно

$$p2^i = 2^{i-k}(n+1)\ln 2.$$

По неравенству Чебышёва вероятность того, что количество отобранных множеств вдвое превысит свое среднее значение, меньше $1/2$. Поэтому достаточно доказать, что второе условие выигрыша первого игрока (после некоторого хода найдётся х, принадлежащее не менее чем $2^k$ множествам первого игрока, но не принадлежащее ни одному из отобранных множеств) выполнено с вероятностью не более $1/2$.

Нам достаточно доказать, что для любого фиксированного х это условие выполняется с вероятностью меньше $2^{-n-1}$. Для этого покажем индукцией по $t$, что вероятность события «после некоторого хода второго игрока слово х принадлежит не менее чем $t$ множествам первого игрока, но не принадлежит ни одному из отобранных множеств» не превосходит $(1-p)^t$. Обозначим это событие через $R_t$. Для $t=0$ утверждение очевидно. Чтобы сделать индуктивный переход, нам достаточно показать, что вероятность $R_{t+1}$ при условии $R_t$ не больше $1-p$.

Пусть $z = (z_1, z_2, \dots, z_s)$ — произвольная последовательность первых $s$ ходов второго игрока ($z_i = 1$, если $i$-е множество первого игрока отбирается, и $z_i = 0$ в противном случае). Будем называть последовательность $z$ неудачной, если после $s$-го хода второго игрока слово $x$ впервые оказалось покрыто $t$ множествами первого игрока и не покрыто ни одним из отобранных множеств (из этого следует, что $s$-е множество первого игрока содержит $x$ и $z_s = 0$). Неудачные последовательности попарно не согласованы и каждая последовательность ходов второго игрока, принадлежащая событию $R_t$ начинается с некоторой неудачной последовательности. Поэтому события «стратегия второго игрока сделала ходы $z = (z_1, z_2, \dots, z_s)$»
для неудачных z образуют разбиение события $R_t$. Значит нам достаточно доказать, что для любой неудачной последовательности z вероятность события $R_{t+1}$ при условии, что второй игрок сделал ходы z, не больше $1-p$. Эта условная вероятность есть вероятность того, что выигрышная стратегия первого игрока в ответ на ходы $z_1, \dots, z_s$ и случайные последующие ходы второго игрока в некоторый момент выдаст множество, содержащее х, а второй игрок не отберёт его. Поскольку решение не отбирать это множество принимается с вероятностью $1-p$ (независимо от предыстории игры), оцениваемая вероятность равна произведению $1-p$ и вероятности того, что первый игрок в ответ на ходы $z_1, \dots, z_s$ и случайные последующие ходы второго игрока в некоторый момент выдаст множество, содержащее х. Следовательно, она не превосходит $1-p$.

Осталось заметить, что $p$ было выбрано таким образом, чтобы при $t = 2^k$ величина $(1-p)^t$ была меньше $2^{-n-1}$.

**Конструктивное доказательство.** Рассмотрим ту же самую игру, только верхнюю границу количества отобранных множеств

$$2^{i-k+1}(n+1)\ln 2$$

заменим на

$$2^{i-k}i^2n\ln 2$$

и разрешим второму игроку на каждом ходу отбирать несколько множеств (из множеств, указанных первым игроком на предыдущих ходах). Укажем явно выигрышную стратегию второго игрока в этой игре. Она состоит из независимого применения $i$ стратегий, занумерованных числами $1, 2, \dots, i$.

Стратегия номер $s$ просыпается через каждые $2^s$ ходов первого игрока, а именно, после любого хода, номер которого кратен $2^s$. Проснувшись, она формирует семейство $S$, состоящее из последних $2^s$ множеств первого игрока, и множество $T$, состоящее из всех слов, которые покрыты не менее $2^k/i$ множествами из $S$. Затем она отбирает некоторые множества из $S$ таким образом, чтобы все слова из $T$ оказались покрыты отобранными множествами. Применяя жадный алгоритм (берем множество из $S$, покрывающее наибольшее количество слов из $T$, затем множество, которое покрывает наибольшую часть остатка и т. д.), мы можем сделать это, отобрав не более

$$\text{in } 2^{s-k} \ln 2$$

множеств. Действительно, каждое слово из $T$ покрыто не менее, чем $2^k/i$ множествами из $S$. Поэтому некоторое множество из $S$ покрывает не менее $|T|2^{k-s}/i$ слов из $T$. Значит, и жадный алгоритм выберет множество, покрывающее не менее этого количества слов. Аналогичные рассуждения применимы и к остатку $T$: второе множество, выбранное жадным алгоритмом, покрывает не менее $2^{k-s}/i$ доли остатка $T$. Поэтому количество элементов $T$, оставшихся не покрытыми после выбора $\text{in } 2^{s-k} \ln 2$ множеств, не превосходит

$$|T|(1-2^{k-s}/i)^{\text{in } 2^{s-k} \ln 2} < 2^n e^{(-2^{k-s}/i)\text{in } 2^{s-k} \ln 2} = 1,$$

то есть непокрытых элементов не останется. (Можно было бы применить и вероятностное рассуждение, показав, что случайно выбранные $\text{in } 2^{s-k} \ln 2$ множеств из $S$
с положительной вероятностью покрывают $T$. Но в этом случае стратегия стала бы менее явной.)

Таким образом, общее количество множеств, отобранных стратегией с номером $s$, не превосходит

$$in2^{s-k}(\ln 2)2^{i-s} = in2^{i-k} \ln 2,$$

что дает в целом не более $i^2 n 2^{i-k} \ln 2$ отобранных множеств.

Осталось доказать, что после каждого нашего хода любое слово, принадлежащее не менее чем $2^k$ множествам первого игрока, покрыто некоторым отобранным множеством. Рассмотрим ход номер $t$ и любое непокрытое после этого хода слово х. Разложим $t$ в двоичную запись: $t = 2^{s_1} + 2^{s_2} + ...$ (где $s_1 > s_2 > ...$). Поскольку х не принадлежит множествам, отобранным стратегиями с номерами $s_1, s_2, ...$, кратность х среди первых $2^{s_1}$ множеств меньше $2^k/i$, кратность х среди следующих $2^{s_2}$ множеств также меньше $2^k/i$ и т.д. Таким образом, после хода $t$ слово х покрыло менее чем $i \cdot 2^k/i = 2^k$ множествами первого игрока. ►

Как и в случае неограниченного класса гипотез, из этой теоремы следует теорема об упрощении гипотез, содержащих «лишнюю» информацию.

**Теорема 259.** Пусть семейство $\mathcal{A}$, из которого выбираются гипотезы, перечислимо. Если слово $x$ имеет $(i \ast j)$-описание $A \in \mathcal{A}$, для которого $KS(A|x) \ge k$, то $x$ имеет и $((i-k) \ast j)$-описание из $\mathcal{A}$ (и, следовательно, $(i \ast (j-k))$-описание, если семейство $\mathcal{A}$ удовлетворяет условию (3) на с. 484).

(Как и раньше, мы опускаем логарифмические слагаемые, необходимые в точной формулировке.)

## 14.5. Дефект оптимальности и дефект случайности

Мы рассматривали две характеристики конечного множества $A$, содержащего слово $x$: (а) дефект случайности $d(x|A) = \log|A| - KS(x|A)$ и (б) разность $\log|A| + KS(A) - KS(x)$, которая показывает, насколько длина двухчастного описания слова $x$ с помощью множества $A$ отличается от минимально возможной. Эту разность мы будем называть дефектом оптимальности гипотезы $A$ о слове $x$ и обозначать $\delta(x|A)$.

Как связаны две эти характеристики? Начнём с очевидного наблюдения:

**Теорема 260.** Дефект случайности слова $x$ относительно конечного множества $A$, содержащего это слово, не превосходит дефекта оптимальности (с логарифмической точностью):

$$d(x|A) \le \delta(x|A) + O(\log l(x)).$$

◀ Нам нужно доказать, что

$$\log|A| - KS(x|A) \le \log|A| + KS(A) - KS(x) + O(\log l(x)).$$

После сокращения $\log|A|$ мы получаем неравенство

$$KS(x) \le KS(A) + KS(x|A) + O(\log l(x));$$
правая часть его (с логарифмической точностью) есть сложность пары $\langle x, A \rangle$ и
потому не меньше $KS(x)$. ►

Как видно из этого рассуждения, разница между дефектом случайности и де-
фектом оптимальности равна $KS(x, A) - KS(x)$, то есть $KS(A|x)$ с точностью
$O(\log l(x) + \log KS(A))$, что есть $O(\log l(x))$, если $KS(A) = O(KS(x))$. (Более
сложных гипотез мы рассматривать не будем: какой смысл в объяснении, которое
значительно сложнее объясняемого объекта?)

Легко привести пример гипотезы, для которой дефект оптимальности значи-
тельно больше дефекта случайности. Например, для случайного слова х длины n
рассмотрим гипотезу B, состоящую из всех слов длины n, и добавим в B случай-
ное слово у длины n - 1, независимое от х. Тогда $KS(B|x)$ примерно равно n,
и дефект оптимальности превосходит дефект случайности (который по-прежнему
близок к нулю, несмотря на добавление слова у) примерно на n. Видно, что в этом
случае гипотеза «плоха» с интуитивной точки зрения, поскольку содержит явно
бессмысленный элемент у, никакого отношения к наблюдаемому х не имеющий;
удаление у позволило бы улучшить гипотезу, приблизив дефект оптимальности к
дефекту случайности (который практически не меняется).

Доказанная нами теорема 256 говорит, что нечто подобное можно сделать все-
гда: если для данной гипотезы B, объясняющей слово х, дефект оптимальности
$\delta(x|B)$ больше дефекта случайности $d(x|B)$ (на величину $KS(B|x)$, как мы зна-
ем), то можно найти другую гипотезу A (не большей сложности, чем B), дефект
оптимальности $\delta(x|A)$ которой не превосходит $d(x|B)$.

Поэтому вопрос о том, можно ли для данного х найти гипотезу А с $KS(A) \le \alpha$
и $d(x|A) \le \beta$, который мы задавали в определении $(\alpha, \beta)$-стохастичности, равно-
силен (с логарифмической точностью) вопросу о том, можно ли найти гипотезу А
с $KS(A) \le \alpha$ и $\delta(x|A) \le \beta$.

**361** Докажите, что (для данного слова х) устройство множества $P_x$ (см. теорему 253) полностью определяет, при каких $\alpha$ и $\beta$ слово х является $(\alpha, \beta)$-стохастическим: это будет, если точка $(\alpha, KS(x) - \alpha + \beta)$ принадлежит $P_x$ или $\alpha > KS(x)$ (как всегда, с логарифмической точностью).

**362** Выведите отсюда обещанное выше (с. 474) утверждение о том, что если $\alpha + \beta < n - O(\log n)$, то существуют слова длины $n$, не являющиеся $(\alpha, \beta)$-стохастическими. [Указание. Таковым будет первое (в алфавитном порядке) слово длины $n$, не имеющее $\alpha * (n - \alpha)$ описаний (если быть точным, то из параметров надо вычество величины порядка $O(\log n)$). Его сложность примерно равна $\alpha$, и можно сослаться на критерий из предыдущей задачи.]

**363** Докажите, что среди слов длины $n$ доля не-$(\alpha, \beta)$-стохастических слов не меньше $2^{-\alpha-\beta-O(\log n)}$. [Указание. Таковыми будут первые $2^{n-\alpha-\beta}$ слова длины $n$ (в алфавитном порядке), не имеющие $\alpha * (n - \alpha)$-описаний (мы опускаем логарифмические слагаемые). Сложность любого из этих слов не меньше $\alpha$ и не больше $\alpha + (n - \alpha - \beta) = n - \beta$. Из второго следует, что для каждого из этих слов х точка $(\alpha, KS(x) - \alpha + \beta)$ не принадлежит $P_x$.]
**364** Докажите, что первое неравенство из условия теоремы 251 можно заменить на более слабое неравенство $\alpha + \beta < n - O(\log n)$. [Указание. Доказательство верхней оценки почти не изменяется: припорная вероятность слова, существующего по задаче 362, не меньше $2^{-\alpha}$. Доказательство нижней оценки в теореме 250 использовало только неравенство $\alpha < \beta - O(\log n)$.]

**365** Для данного слова $x$ рассмотрим множество $Q_x$, состоящее из пар $\langle\alpha, \beta\rangle$, для которых слово $x$ является $(\alpha, \beta)$-стохастическим. Докажите, что граница множества $Q_x$ является (с логарифмической точностью) невозрастающей кривой, ведущей из точки некоторой точки $\langle 0, i \rangle$, где $i \le l(x) - KS(x)$, в точку $\langle KS(x), 0 \rangle$, и что любая простая невозрастающая кривая может являться такой границей.

**366** Докажите, что если для данного слова $x$ и данного $\alpha$ существует гипотеза, доставляющая минимум дефекта случайности среди гипотез сложности не выше $\alpha$, но её дефект оптимальности превосходит её дефект случайности на $\gamma$, то граница множества $P_x$ на участке от $\alpha - \gamma$ до $\alpha$ (считая по оси абсцисс) идёт под углом $45^\circ$. [Указание. Воспользуйтесь более сильным утверждением теоремы 256.]

**367** Пусть $\mathcal{A}$ — любое семейство конечных множеств слов, удовлетворяющее условиям (1)–(3) на с. 484. Докажите, что для любого $x$ и любого $\alpha \le KS(x)$ утверждения «существует множество $A \in \mathcal{A}$ сложности не более $\alpha$ с $d(x|A) \le \beta$», «существует множество $A \in \mathcal{A}$ сложности не более $\alpha$ с $\delta(x|A) \le \beta$» и «точка $\langle\alpha, KS(x) - \alpha + \beta\rangle$ принадлежит $P_x^{\mathcal{A}}$» эквивалентны (с логарифмической точностью).

**368** Пусть $\mathcal{A}$ — произвольное семейство конечных множеств, перечисляемое программой $p$. Докажите, что для любого $x$ длины $n$ утверждения «существует множество $A \in \mathcal{A}$ с $d(x|A) \le \beta$» и «существует множество $A \in \mathcal{A}$ с $\delta(x|A) \le \beta$» эквивалентны (с точностью $O(l(p) + \log KS(A) + \log n + \log \log |A|)$).

## 14.6. Минимальные гипотезы

Пусть фиксировано некоторое слово $x$. Ему, как мы видели, соответствует множество $P_x$ пар $(\alpha, \beta)$, для которых $x$ имеет $(\alpha * \beta)$-описание. Такие описания, как мы говорили, естественно рассматривать как «статистические гипотезы», объясняющие происхождение слова $x$. Интересно понять, как именно устроены эти гипотезы. Оказывается, что можно более или менее явно описать некоторый класс гипотез, к которым в некотором смысле сводится любая гипотеза. Этот класс проистекает из доказательства теоремы 254.

Пусть $l$ — произвольное число, большее $KS(x)$. Тогда перечень всех слов сложности не более $l$ содержит $x$. Фиксируем такой перечень (простой алгоритм, рождающий все эти слова по одному разу). Пусть $N_l$ — число слов в перечне. Запишем $N_l$ в двоичной системе счисления, то есть представим его в виде суммы убывающих степеней двойки:

$$N_l = 2^{s_1} + 2^{s_2} + \dots + 2^{s_t}, \text{ где } s_1 > s_2 > \dots > s_t.$$
В соответствии с этим разложением и перечень можно разбить на группы в порядке порождения элементов: сначала идут $2^{51}$ элементов, затем $2^{52}$ элементов и так далее. Слово х попадает в одну из частей. Эту часть (соответствующее конечное множество) мы и будем рассматривать как описание слова х. Таким образом, мы получаем некоторое семейство описаний (при каждом $l > KS(x)$ — своё описание).

Следующие две теоремы устанавливают обещанные свойства этих описаний (во-первых, они являются минимальными, то есть лежат на границе множества $P_x$; во-вторых, всякое описание слова х в некотором смысле сводится к одному из них).

**Теорема 261.** Пусть в описанной ситуации слово х попало в часть размера $2^s$. Тогда эта часть является $((1-s) * s)$-описанием и точка $(1-s, s)$ лежит на границе множества $P_x$ (точнее говоря, она является $((1-s+O(\log l)) * s)$-описанием и соответствующая точка лежит в $O(\log l)$-окрестности границы множества $P_x$).

◀ Чтобы задать часть, достаточно знать её размер, а также сколько элементов имеется перед ней, то есть достаточно знать $s$, $l$ и все биты числа $N_l$, кроме $s$ последних (то есть $l-s$ битов). Ещё нужно знать сам перечень, но он по предположению имеет логарифмическую сложность. Поэтому сложность рассматриваемой части есть $l-s+O(\log l)$, а число элементов в ней равно $2^s$, что и требовалось.

Если бы точка $(1-s, s)$ не лежала бы на границе множества $P_x$, а входила бы в $P_x$ вместе с некоторой окрестностью более чем логарифмического размера, то слово х имело бы заметно лучшие двухчастные описания, чем построенное нами (с той же или даже немного меньшей суммарной длиной и с большим размером множества) и по теореме 254 (пункт (г)) слово х появлялось бы в перечне более чем за $2^s$ элементов до конца (что противоречит построению части). ▶

Следующая теорема показывает, что описаний рассмотренного вида в некотором смысле достаточно. Пусть даны произвольное слово х и произвольное конечное множество $A$, его содержащее. Пусть максимальная сложность слов из $A$ равна $l$. Как и раньше, разобьём слова сложности не выше $l$ (их число обозначим $N_l$) на части, размеры которых есть степени двойки, соответствующие единичным битам в двоичной записи $N_l$. Пусть $B$ — часть, в которую попало слово х, и пусть она имеет размер $2^s$.

**Теорема 262.** Гипотеза В (как объяснение для слова х) не хуже гипотезы А с точки зрения зрения сложности и дефекта оптимальности:

(а) $KS(B) \le KS(A)$;

(б) $\delta(x|B) \le \delta(x|A)$ (с точностью $O(\log l)$). Кроме того,

(в) $KS(B|A) = O(\log l)$ (гипотеза В проста относительно А).

◀ Зная А и значение $l$, мы можем дождаться, когда в перечне всех сложности не больше $l$ появятся все слова из множества А. К этому моменту появится и слово х (входящее в часть размера $2^s$), так что останутся необнаруженными не более $O(2^s)$ слов (из этой и следующих частей). Таким образом, мы знаем $N_l$ с ошибкой не более чем $O(2^s)$ и тем самым знаем его первые $l-s$ его битов с ошибкой $O(1)$. А по этой информации (а также $l$ и $s$) мы можем получить В. Таким образом, $KS(B|A) = O(\log l)$. Утверждение (в) (а тем самым и (а)) доказано.
Утверждение (б) очевидно по построению: если $KS(A) = \alpha$ и $\log|A| = \beta$, то все слова множества $A$ имеют $(\alpha * \beta)$-описание и сложность не более $\alpha + \beta + O(\log \alpha)$, так что и максимальная сложность $l$ не превосходит $\alpha + \beta + O(\log \alpha)$. Построенное двухчастное описание, как мы видели в предыдущей теореме, является $((l-s) * s)$-описанием, так что его суммарная длина (и потому дефект оптимальности) не больше, чем у $A$. ►

Связь между параметрами гипотез $A$ и $B$ в этой теореме показана на рис. 14.3: точка изображает параметры гипотезы $A$, а серым цветом показана область, где могут находиться параметры гипотезы $B$.

<figure><img src="image_54.png" /><figcaption>Рис. 14.3. Параметры гипотезы $A$ и её «упрощения» $B$.</figcaption></figure>

Что будет, если начальная гипотеза $A$ сама уже была минимальной (близкой к границе множества $P_x$)? Можно ли утверждать, что $B$ в этом случае имеет те же параметры, что и $A$? Вообще говоря, нет: возможно, что гипотеза $B$ находится на пунктирной границе серой области (рис. 14.3). (Внутри серой области она находиться не может, поскольку в этом случае гипотеза $A$ была бы, как легко проверить, внутренней для $P_x$.)

Можно сказать ещё и так: если представлять себе границу множества $P_x$ как кривую, идущую поочерёдно вправо-вниз (под углом $45^\circ$) и вертикально вниз, то все точки поворота, в которых вертикальное движение сменяется наклонным, имеют соответствующие им гипотезы нашего семейства (поскольку для таких $A$ серая область, в которой может находиться $B$, пересекается с $P_x$ в единственной точке).

Заметим, что информация, содержащаяся в гипотезах построенного нами семейства, как это ни странно, почти не зависит от слова $x$: гипотеза $B$ содержит ту же информацию, что и начало слова $N_l$ длины $l-s$. Как мы видели в задаче 354 (с. 483), это начало можно заменить на слово $N_{l-s}$ или (теорема 116, с. 195) на начальный отрезок числа Чейтина $\Omega$. Тем самым наши гипотезы (по мере движения по границе $P_x$ слева направо) содержат всё больше и больше битов числа $\Omega$. Выходит, что гипотезы семейства содержат всё больше и больше информации не только об $x$ (что хорошо), но и о числе $\Omega$ (которое от $x$ не зависит).

Возможно, кроме логарифма размера и сложности, у гипотез имеются и другие неизученные нами параметры, с помощью которых можно разделить гипотезы одинакового размера и сложности на более и менее подходящие для объяснения $x$. В качестве такого параметра в работе [172] предложено рассмотреть тоталь-
ную сложность гипотезы А при известном х. Во всех примерах, рассмотренных нами, интуитивно правильные гипотезы для объяснения х имеют малую тотальную сложность относительно х. С другой стороны, можно показать, что гипотезы «универсального» из теоремы 261 имеют большую тотальную условную сложность относительно некоторых своих элементов (хотя и маленькую обычную условную сложность). Мы не будем доказывать этого утверждения, отсылая читателя к [172].

Ещё интересно отметить, что это наблюдение (о том, что одна гипотеза содержит часть информации из другой) относится лишь к построенным нами гипотезам, а не к произвольным гипотезам на границе множества $P_x$. Это показывает следующий пример. Пусть х — случайное слово длины n. Рассмотрим две следующих гипотезы: множество слов длины n, имеющих ту же первую половину, что у х, и множество слов длины n, имеющих ту же вторую половину, что у х. Обе гипотезы имеют совсем небольшой дефект оптимальности, однако содержат разную информацию. (Это не противоречит доказанной теореме, поскольку в качестве гипотезы В, которая лучше обеих, может фигурировать множество всех слов длины n.)

## 14.7. Немного философии

Задачу поиска двухчастного описания для данного слова х можно разукрашивать по-разному. Можно говорить о науке, которая наблюдает внешний мир в лице слова х и строит о нём разные гипотезы, пытаясь отобрать «наиболее правильную». При этом критерием отбора является простота гипотезы (измеряемая колмогоровской сложностью множества А; чем эта сложность меньше, тем гипотеза проще, то есть лучше), а также её «конкретность», или «объясняющая способность» (которая измеряется размером множества А; чем оно меньше, тем гипотеза конкретнее, то есть лучше). Под это дело можно даже подвести философскую базу в лице классика философии Оккама и его бритвы, согласно которой не следует умножать сущности без надобности. Ещё можно стремиться к тому, чтобы дефект случайности наблюдаемого слова х относительно предложенной гипотезы А был мал («не оставалось необъяснённых закономерностей»).

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

Это относится к сжатию без потерь информации. Однако всё большее применение находят способы сжатия, где некоторая «несущественная» часть информации теряется и за счёт этого достигается большее сжатие.

Пусть, скажем, есть старая граммофонная пластинка, на которой от долгого хранения в пыльном чулане появились царапины (в случайных местах дорожки, содержащей запись). Царапины соответствуют различным паразитным пикам на осциллограмме сигнала (графике зависимости звукового давления от времени). Таким образом, изначальная информация подверглась случайному искажению. Сложность
записи при этом сильно возросла, если царапин много. Но если мы хотим передать лишь общее впечатление от проигрывания этой пластинки, то нам неважно, где именно находятся царапины, а важен лишь общий характер дефектов.

Другими словами, фактическая запись на пластинке является одним из элементов большого множества записей с «такого же типа царапинами». Тем самым получается двухчастное описание: сначала мы задаём это множество (скажем, указав начальную неискажённую запись и статистические характеристики наложенного шума), а затем указываем конкретный элемент этого множества (где именно царапины). Если при сжатии мы утратим вторую часть описания, сохранив лишь первую, то после восстановления мы получим запись, где на тот же исходный сигнал будет наложен шум с теми же статистическими характеристиками, но уже другой. Можно ожидать, что слушатель не заметит этой подмены. А если удастся шум вообще не накладывать, тем самым «очистив» запись, это ещё лучше (если нас интересует музыка, а не ностальгическое очарование старинного граммофона).

Пользуясь этой аналогией, можно следующим образом интерпретировать утверждение задачи 368. Пусть слово х было получено из неизвестного слова у той же длины наложением шума, то есть для некоторого известного нам r слово х было выбрано случайно в шаре Хемминга радиуса r с центром у. Желая удалить шум, мы ищем шар Хемминга радиуса r, дающий минимально короткое двухчастное описание для х (то есть шар минимальной сложности). Допустим нам это удалось, и мы в самом деле нашли шар минимально возможной сложности. С большой вероятностью дефект случайности х в исходном шаре мал, а значит, по задаче 368 (примененной к семейству, состоящему из множества шаров Хемминга радиуса r) мал будет и дефект оптимальности х в найденном нами шаре. Это означает, что в найденном двухчастном описании х вторая часть не содержит полезной информации. Иными словами, центр найденного шара является очищенной от шума версией х (в частности, и от того шума, который уже был в у).

Другой пример: в фотографии, скажем, песчаной гряды, сделанной с большим разрешением, зафиксированы положения отдельных песчинок, которые случайны, и потому сложность этой фотографии велика. Однако для зрителя она является всего лишь «типичным элементом» множества фотографий, где песчаная гряда находится на том же месте и сложена из такого же песка, хотя конкретные песчинки могут быть в разных местах. Если при сжатии сохранится только информация об этом множестве, а при восстановлении будет построен другой типичный его элемент, то разница будет незаметна.

Надо иметь в виду, что эта аналогия — всего лишь аналогия, причём довольно далёкая, и вряд ли математические результаты о колмогоровской сложности двухчастных описаний могут найти непосредственные «практические применения». (Хотя бы потому, что мы полностью игнорируем вычислительную сложность алгоритмов декодирования, а алгоритмы кодирования вообще не рассматриваем. Может быть, именно этим объясняется парадоксальная независимость оптимальных гипотез от слова х, которую мы отмечали выше.)
Приложение 1. Колмогоровская сложность и
основания теории вероятностей

В этом разделе мы не формулируем и не доказываем никаких математических утверждений, а обсуждаем основания теории вероятностей, в том числе и роль алгоритмической теории информации, следуя [156].

Парадокс теории вероятностей

Часто говорят, что в естественных науках учёный выдвигает гипотезы, которые затем поверяет экспериментом: если эксперимент не согласуется с предсказаниями, полученными на основе гипотезы, то нужно её отбросить или изменить.

Можно ли эту схему применить к теории вероятностей? Предположим, что мы высказали гипотезу «честной монеты» (бросания независимы и орлы и решки равновероятны), а затем тысячу раз бросали монету, чтобы эту гипотезу проверить. Получилась последовательность орлов и решек (нулей и единиц) длины 1000. Но как можно о чём-то судить на основании этой последовательности, если гипотеза как раз и утверждает, что все 2¹⁰⁰⁰ последовательностей длины 1000 равновероятны? Разве могут в этом случае одни из них опровергать гипотезу, а другие — подтверждать? Или все они равновероятны, но некоторые менее равновероятны (как мог бы сказать Оруэлл)?

Вот другая ситуация, где возникает тот же парадокс. Предположим (говорят, так и было в XIX веке), что колоды карт продаются запечатанными и предварительно перетасованными, чтобы можно было распечатать колоду и начать игру. Идея хорошая (если вы не шулер), но для её реализации нужно тасовать колоды перед отправкой их потребителям. Как и любой технологический процесс, тасование карт нуждается в контроле: ОТК должен просматривать колоды, и хорошо перетасованные пропускать, а плохо перетасованные отправлять на дотасовку. Но что такое «плохо» и «хорошо» перетасованные? Ведь идея тасования в том и состоит, чтобы сделать все *n*! расположений карт равновозможными!

Более современный вариант того же парадокса. Составители теста для школьников, где в 20 вопросах надо отгадать один из двух правильных ответов<fnref n="1" /> «а» или «б», хотят изготовить для каждого школьника индивидуальный вариант, случайно переставляя ответы. В одном из вариантов случайно оказалось, что правильны все двадцать ответов «а». Надо ли забраковать этот вариант?

<footnote n="1">¹ Мы оставляем в стороне вопрос об осмысленности таких тестов.</footnote>
## Сложившаяся практика

Что бы там ни говорили философы, статистики — люди практические и им работать надо. Попробуем описать, как такая работа происходит [167, 151, 156].

**А. Применение статистических гипотез.** Прежде всего надо признать, что теория вероятностей не делает предсказаний, а даёт рекомендации. Рекомендации эти основаны на следующем: если рассчитанная (на основе принятой гипотезы) вероятность события А много меньше, чем вероятность события В, то возможность осуществления события В надо рассматривать в первую очередь и в гораздо большей степени, чем возможность осуществления события А. (Мы предполагаем, что последствия двух этих событий одинаково серьёзны.) В частности, если вероятность А меньше вероятности попасть под метеорит, то скорее всего А можно игнорировать полностью (поскольку В так и так приходится игнорировать, иначе жить нельзя).

Борель [12] формулирует этот принцип так: «...В Париже меньше миллиона взрослых людей [это сейчас уже не так]; газеты ежедневно извещают о странных случаях или несчастьях, постигших одного из них; жизнь была бы невозможной, если бы каждый постоянно опасался за себя в отношении всех приключений, о которых можно прочесть в отделе разных происшествий; а это равносильно тому, чтобы сказать, что практически нужно пренебрегать вероятностями, которые меньше одной миллионной... Часто боязнь дурного приводит к ещё худшему. Чтобы уметь различить худшее, надо хорошо знать вероятности различных явлений» (с. 159–160).

**Б. Отбор статистических гипотез.** Здесь нельзя наивно утверждать, что если наблюдаемое событие имеет пренебрежимо малую вероятность согласно рассматриваемой гипотезе, то её нужно отбросить. В самом деле, это бы означало, что любой результат тысячи бросаний монеты опровергает её честность, поскольку эта конкретная последовательность орлов и решек имеет вероятность $2^{-1000}$.

Именно в этом месте вступает в игру колмогоровская сложность. Мы отвергаем гипотезу, наблюдая простое событие, которому эта гипотеза приписывает пренебрежимо малую вероятность. Поэтому появление тысячи орлов подряд (ну, или чередование пяти сотен орлов с пятью сотнями решек) воспринимается нами как противоречашее честности монеты.

В этой формулировке важны обе части: «первым выпал орёл» — простое событие, но вероятность его достаточно велика, поэтому оно не противоречит честности монеты. С другой стороны, вероятность появления любой последовательности из тысячи битов пренебрежимо мала, но если эта последовательность не проста, это тоже не противоречит честности монеты.

Иногда правило отбора статистических гипотез и правило их применения объединяют в одной формулировке: «события с малой вероятностью достоверно не происходят». Вот как пишет про это Борель: «Не следует бояться применить слово достоверность для обозначения вероятности, которая отличается от единицы на достаточно малую величину» ([13], с. 7). Иногда эту формулировку называют принципом Курно. Но мы предпочитаем разделять эти две стадии, поскольку при