Вычислительно трудные задачи и дерандомизация

Представим себе, что есть явная вычислительная задача, про которую достоверно известно, что ее нельзя решить за разумное время. Хорошо это или плохо? С одной стороны, грустно, наверное, мы никогда не сможем решать эту задачу. С другой стороны, не только мы, но и враг не сможет решить эту задачу за разумное время и можно попытаться использовать это задачу для надежного шифрования данных, чтобы враг не смог взломать шифр, не решив задачу. Это идея появилась давно и попытки строить криптографические протоколы на основе вычислительно трудных задач начались в 1970–х годах.

Другая неожиданная польза от вычислительно трудных задач была открыта в конце 1990–х — начале 2000–х. И этот результат является одним из самых ярких результатов в теоретической информатики последних лет (и является основным в этом курсе). Оказывается, имея явную вычислительно трудную задачу, можно избавиться от случайных чисел в вероятностных алгоритмах. Ситуация в мире вычислений такая: либо любой вероятностный алгоритм можно дерандомизировать избавиться от использования случайных чисел), либо не существуют явных вычислительно сложных задач.

Под явной задачей имеется в виду задача, которую можно решить за экспоненциальное время, а под вычислительно трудной — такая, которая не решается с помощью булевых схем полиномиального размера. Хотя случайная булевая функция с большой вероятностью решается только схемами экспоненциального размера, ни для какой явной функции мы доказывать это не умеем. Курс начнется с самых красивых примеров экспоненциальных нижних оценок в ограниченных (в неограниченных же не получается!!) моделях вычислений: монотонные схемы (за этот результат А. Разборов получил премию Неванлинны), схемы ограниченной глубины и др. Продемонстрировав существующую технику доказательств нижних оценок, мы поговорим о философской и полемической работе А. Разборова и С. Рудича “Natural proofs” (авторы удостоились премии Гёделя в 2007–м году за этот результат), основной результат которой заключается в том, что существующая техника оказательства нижних оценок является «естественной», а при разумных криптографических предположениях, естественных доказательств недостаточно для того, чтобы доказать нетривиальную нижнюю оценку для схем.

Вторая часть курса будет посвящена непосредственно дерандомизации (избавлению алгоритмов от случайных чисел). Будут приведены результаты о том, как можно понижать вероятность ошибки алгоритма, используя лишь небольшое число дополнительных случайных битов, будет рассказан детерминированный (дерандомизация вероятностного) алгоритм Рейнгольда выхода из лабиринта, использующий только логарифмическую (от размера лабиринта) память, будут приведены конструкции экстракторов, графские конструкции, позволяющие использовать «плохие» (зависимые, неравномерно распределенные) случайные биты в алгоритмах. И главным результатом этой части будет дерандомизация при условии cуществования функции, вычислимой за экспоненциальное время, которая не вычислима с помощью схем полиномиального размера.

В доказательствах основных результатов курса будет использоваться и подробно обсуждаться глубокая современная техника: random restriction lemma, error–correcting codes, Impagliazzo hardcore lemma, Yao XOR lemma, графы–расширители и пр. Понимание этой техники может существенно облегчить чтение статей по теоретической информатики.

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