Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Вычислительно трудные задачи и дерандомизация
Санкт-Петербург / весна 2009, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

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

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

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

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

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

Дата и время Занятие Место Материалы
15 февраля
10:10–11:40
Теорема Разборова о нижней оценке на сложность монотонных схем, Лекция ПОМИ РАН слайды
22 февраля
10:10–11:40
Нижние оценки для схем ограниченной глубины, Лекция ПОМИ РАН слайды
15 марта
10:10–11:40
Еще одна нижняя оценка для схем ограниченной глубины (теорема Разборова–Смоленского), Лекция ПОМИ РАН слайды
15 марта
11:50–13:20
Естественные доказательства (natural proofs), Лекция ПОМИ РАН слайды
22 марта
10:20–11:50
Псевдослучайный генератор Нисана–Вигдерсона, Лекция ПОМИ РАН слайды
12 апреля
10:20–11:50
Повышение трудности функций: лемма Импальяццо о трудном распределении, XOR лемма Яо, Лекция ПОМИ РАН слайды
12 апреля
12:00–13:30
Псевдослучайный генератор Нисана–Вигдерсона (окончание). Конструкция дизайна, Лекция ПОМИ РАН слайды
19 апреля
10:20–11:50
Повышение трудности функций: коды, исправляющие ошибки. Коды Рида–Соломона, Уолша–Адамара, Рида–Мюллера. Локальное декодирование, Лекция ПОМИ РАН слайды
26 апреля
10:25–11:55
Уменьшение вероятности ошибки с помощью блуждания по экспандеру, Лекция ПОМИ РАН слайды
03 мая
10:25–11:55
Экстракторы: существование, конструкция из случайного блуждания по экспандеру, Лекция ПОМИ РАН слайды
10 мая
10:25–11:55
Дерандомизация вычислений с логарифмической памятью, Лекция ПОМИ РАН слайды
10 мая
12:00–13:30
Экстрактор из псевдослучайного генератора, Лекция ПОМИ РАН слайды