Импальяццо и Вигдерсон: а нужна ли она вообще

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

Вопрос

Обозначим через $\mathrm{P}$ задачи, решаемые за полиномиальное время обычным алгоритмом, а через $\mathrm{BPP}$ — задачи, решаемые за полиномиальное время алгоритмом, которому разрешено бросать монету и ошибаться с вероятностью не больше $1/3$. (Ошибку легко сбить до $2^{-k}$: прогнать алгоритм $k$ раз и взять большинство.)

Верно ли, что $\mathrm{P} = \mathrm{BPP}$?

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

Как убрать монету

Пусть алгоритм тратит $r$ случайных битов. Тогда его можно сделать детерминированным грубой силой: перебрать все $2^r$ наборов случайных битов, прогнать алгоритм на каждом и взять ответ большинства. Правильно, но дорого: $2^r$ прогонов, а $r$ обычно порядка длины входа.

А если бы удалось не брать все $2^r$ наборов, а разворачивать длинную «почти случайную» строку из короткого зерна? Тогда перебирать надо было бы только зёрна. При длине зерна $O(\log n)$ перебор — это $2^{O(\log n)} = n^{O(1)}$, то есть полиномиальный. Монета убрана.

Значит, дерандомизация — это генератор псевдослучайных чисел с логарифмическим зерном. Но у криптографических генераторов зерно длинное, и короче быть не может.

Хитрость Нисана и Вигдерсона

Разница обнаружилась в 1988 году, и она тонкая, но решающая.

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

А генератору для дерандомизации нужно обмануть один заранее известный алгоритм с заранее известным полиномиальным временем работы. И тут разрешено то, что немыслимо в криптографии: генератор может работать дольше, чем тот, кого он обманывает. Это послабление и позволяет ужать зерно до логарифма.

Осталось из чего-то строить. Строят из трудности: если есть задача, которую нельзя решить маленькой схемой, её ответы для генератора выглядят непредсказуемыми.

Теорема (1997)

Если в классе $\mathrm{E}$ существует задача, требующая схем размера $2^{\Omega(n)}$, то $\mathrm{P} = \mathrm{BPP}$.

Прочитаем это по-человечески. Трудность превращается в случайность. Если мир устроен так, что в нём есть по-настоящему трудные задачи, — то случайность вычислителю не нужна вовсе; всякий вероятностный алгоритм переделывается в обычный с той же полиномиальной скоростью.

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

Почему в это верят и чего не хватает

Посылку никто не доказал. Больше того, нижние оценки на размер схем — самое слабое место всей теории сложности: не умеют доказать даже того, что задачам из $\mathrm{NP}$ нужны схемы больше линейного размера. Но в существование трудных задач верят практически все — на этом же стоит вся криптография.

Поэтому большинство специалистов считает, что $\mathrm{P} = \mathrm{BPP}$, то есть случайность в алгоритмах — удобство, а не сила. Косвенное подтверждение уже есть: главный вероятностный алгоритм столетия, проверка на простоту, в 2002 году был дерандомизирован — Агравал, Каял и Саксена обошлись без монеты.

И ещё одно, замыкающее. В 2004 году Импальяццо вместе с Кабанцом доказал обратное: если научиться дерандомизировать, то из этого автоматически следуют нижние оценки на схемы. То есть даром $\mathrm{P} = \mathrm{BPP}$ не получить: доказать это — значит доказать то, чего никто не умеет уже полвека.

Где мы оказались

Нить начиналась с вопроса, есть ли случайность на самом деле. Пройдя её до конца, получаем ответ по частям:

• в предсказании случайность неустранима — показал Пуанкаре, нарисовал Лоренц;
• в описании она неустранима — почти всё несжимаемо, и доказать про конкретный объект ничего нельзя;
• в вычислении она, по-видимому, устранима полностью — вот эта теорема;
• в природе она, по-видимому, неустранима — единственное место, где это проверено опытом.

Заметьте, что вопрос по дороге сменился. «Есть ли случай» оказался вопросом не математическим; «что называть случайным» — оказался математическим, и на него есть три сошедшихся ответа; а «нужен ли случай» — оказался вопросом о трудности, и ответ на него, вероятнее всего, отрицательный.

О людях

Ави Вигдерсон (род. 1956) — единственный человек, у которого есть и Абелевская премия (2021), и премия ТьюрингаАлан Тьюринганглийский математик и криптоаналитик · 1912–1954Определил, что значит «вычислить», за десять лет до появления компьютеров, взломал «Энигму» и был осуждён за то, кем он был. (2023). Обе — во многом за эту линию работ: за то, что случайность в вычислениях перестала быть загадкой и стала предметом теории.

Расселл Импальяццо (род. 1963) известен не только теоремами. В 1995 году он описал «пять миров» — пять мыслимых устройств вычислительной вселенной, в зависимости от того, какие гипотезы окажутся верны: мир, где $\mathrm{P} = \mathrm{NP}$ и трудностей нет вовсе; мир, где трудные задачи есть, но только в среднем лёгкие; мир, где трудные задачи есть, а криптографии всё равно нет; и два мира с криптографией разной силы. Мы до сих пор не знаем, в каком из пяти живём, — и от этого зависит в том числе то, нужна ли на самом деле случайность.