Сложность в среднем случае вероятностных вычислений с ограниченной ошибкой тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Ицыксон, Дмитрий Михайлович

• Ицыксон, Дмитрий Михайлович
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Ицыксон, Дмитрий Михайлович

Введение

Сложность в среднем случае и криптография.

Структурная теория сложности в среднем случае.

Сложность обращения функции Голдрейха в среднем случае

Структура диссертации.

1 Основные понятия

1.1 Распределения на входах.

1.2 Полиномиальное в среднем случае время работы.

1.3 Классы распределенных задач поиска.

1.4 Классы распределенных задач распознавания

1.5 Эвристические классы.

1.6 Функции, односторонние для бесконечного числа длин входов

1.7 Функция Голдрейха.

1.8 Алгоритмы расщепления

2 Бесконечно часто односторонние функции, основанные на предположении о сложности в среднем случае

2.1 Сведения распределенных задач поиска.

2.2 Идея доказательства.

2.3 Детали доказательства.

3 Структурная сложность класса AvgBPP

3.1 Сведения распределенных задач распознавания

3.2 Полная задача.

3.2.1 Основная идея.

3.2.2 Детали конструкции.

3.3 Полная задача с равномерным распределением и дерандоми-зация.

3.4 Теорема об иерархии по времени.

3.5 Сложность в среднем и в наихудшем случае.

4 Нижняя оценка на среднее время обращения функции Голдрейха «пьяными» алгоритмами

4.1 Что можно эффективно решать «пьяными» алгоритмами?

4.2 Алгоритмы расщепления и метод резолюций.

4.3 Нижняя оценка для «пьяных» алгоритмов на выполнимых формулах в наихудшем случае.

4.4 Поведение «пьяных» алгоритмов на невыполнимых формулах

4.5 Поведение «пьяных» алгоритмов на выполнимых формулах

4.5.1 Замыкание

4.5.2 Надстройка над «пьяными» алгоритмами.

4.5.3 Оценка числа решений.

4.5.4 Нижняя оценка времени работы.

Введение диссертации (часть автореферата) на тему «Сложность в среднем случае вероятностных вычислений с ограниченной ошибкой»

Вероятностные алгоритмы с ограниченной ошибкой (также известные как алгоритмы Монте-Карло) — это алгоритмы, которые используют случайные числа и для каждого входа с вероятностью хотя бы | выдают правильный ответ. Интерес к вероятностным алгоритмам возрос в 1970-х годах, когда Соловэй и Штрассен опубликовали эффективный вероятностный алгоритм проверки числа на простоту [40]. Гилл [19] дал определение классу сложности ВРР, который состоит из языков, которые могут быть распознаны за полиномиальное время вероятностными алгоритмами с ограниченной ошибкой. Долгое время задача проверки числа на простоту была самым ярким примером задачи, для которой известен эффективный вероятностный алгоритмам, но не известен детерминированный. Однако в 2002 году появилс51 детерминированный полиномиальный по времени тест числа на простоту [3]. На данный момент примером задачи, для которой известен эффективный вероятностный алгоритм, но не известен детерминированный, является задача проверки равенства нулю многочлена, записанного не обязательно в канонической форме.

Вопрос о совпадении классов сложности Р и ВРР является открытым. Результаты современных исследований о связи существования явных труд-норешаемых задач и дерандомизации [35, 6, 29, 41, 39, 42] дают основание для выдвижение гипотезы Р = ВРР (в частности, из существования булевой функции, которая вычислима за время 2сп, но не вычислима с помощью схем размера меньше, чем 2СП, следует, что Р = ВРР).

Р и ВРР — это классы задач, которые можно эффективно решать на практике. Для определения понятия надежности криптографического протокола нужно понимать, что значит, что задачу (взлом протокола) невозможно эффективно решать на практике. Из того, что задача не лежит в классе ВРР, еще не следует, что эту задачу нельзя эффективно решать на практике. Вполне возможно, что для каждой длины входа есть ровно один вход, для которого задача сложна, а для всех остальных входов задача является простой. Именно для нужд криптографии были сформулированы основные понятия теории сложности в среднем случае Левиным [32] и Гуревичем [23] в конце 1980-х годов.

В теории сложности в среднем случае массовые вычислительные задачи рассматриваются вместе с распределением на входах (индивидуальных задачах). Задачи, снабженные распределением, мы называем распределенными задачами. Мы рассматриваем полиномиально моделируемые распределения, т.е. такие, которые могут быть порождены за полиномиальное время с использованием равномерного распределения. Первое определение понятия полиномиального в среднем случае алгоритма дал Левин в [32]. Согласно Левину, алгоритм работает полиномиальное в среднем случае время, если существует такое положительное число е, что математическое ожидание функции Те{х) по всем входам х длины п есть 0{п), где Т(х) — это время работы алгоритма на входе х. Эквивалентное определение дал Импальяццо в [30]; согласно ему, вычислительная задача решается за полиномиальное в среднем время, если для нее существует алгоритм с двумя параметрами х (вход) и 5 (вероятность ответа «не знаю»), время работы которого ограничено полиномом относительно ^ и который отвечает «не знаю» с вероятностью не больше 5 (в противном случае он выдает правильный ответ).

Левин [32] также доказал полноту в среднем случае задачи о замощении. Если задача о замощении может быть решена за полиномиальное в среднем время, то и все NP-задачи с полиномиально моделируемыми распределениями могут быть решены за полиномиальное в среднем время.

Позже было доказано, что следующие распределенные задачи тоже являются полными в среднем случае: задача об ограниченной остановке машины Тьюринга, задача Поста [24], задача декомпозиции матрицы [10] и ДР

Сложность в среднем случае и криптография

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

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

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

• Односторонняя в среднем случае функция.

Есть два способа определить трудность обращения функции на языке сложности в среднем случае.

1. Задача обращения функции / с полиномиально моделируемым распределением на входах / не решается никаким полиномиальным в среднем случае вероятностным алгоритмом с ограниченной ошибкой. В этом случае функцию / называют односторонней в среднем случае.

2. Задача обращения функции / с полиномиально моделируемым распределением на выходах (образах) / не решается никаким полиномиальным в среднем случае вероятностным алгоритмом с ограниченной ошибкой. В этом случае говорят, что задача обращения / — это трудная в среднем случае задача. Существование трудных в среднем случае задач эквивалентно (NP,PSamp) <2 AvgBPP, где (NP,PSamp) — это множество задач из NP с полиномиально моделируемыми распределениями, a AvgBPP — это множество распределенных задач, которые можно решить за полиномиальное в среднем время вероятностными алгоритмами с ограниченной ошибкой (этот факт следует из того, что любую распределенную задачу поиска из NP с полиномиально моделируемым распределением можно свести к задаче поиска с равномерным распределением [28], а любую задачу поиска с равномерным распределением можно свести к некоторой задаче распознавания [8]).

Из существования односторонних в среднем случае функций следует существование трудных в среднем случае задач, поскольку полиномиально моделируемое распределение на входах функции порождает полиномиально моделируемое распределение на выходах функции.

Из существования криптографических односторонних функций следует существование односторонних в среднем функций (это простое следствие эквивалентности существования слабых и сильных односторонних функций [21]), из чего следует существование трудных в среднем задач, что влечет (NP,PSamp) % AvgBPP. Следует ли из (NP,PSamp) % AvgBPP существование криптографически односторонних функций, является важнейшим открытым вопросом. Следует ли из (NP,PSamp) % AvgBPP существование односторонних в среднем случае функций, также является открытым вопросом. Я. Левин в [1] показывает, что если существует трудная в среднем задача обращения функции, сохраняющей длину, с равномерным распределением, то существует и односторонняя в среднем,функция (эти два условия слишком сильные, их не получается удовлетворить, основываясь ни на одной из известных полных задач в классе (NP,PSamp)).

Из существования трудных в среднем случае задач следует существование односторонних функций в наихудшем случае, то есть Р ^ NP. Обратная импликация является открытым вопросом.

Имеются три основных отличия между подходами к задаче обращения функции, принятых в криптографии и в сложности в среднем.

1. Успешный криптографический противник может ошибаться на полиномиальной доле входов [21, определение 2.2.2], в то время как полиномиальный в среднем алгоритм не может тратить экспоненциальное время на полиномиальной доле входов [32, 11].

2. Вероятностное (моделируемое за полиномиальное время) распределение в криптографии берется по прообразу функции (ее входам), а в сложности в среднем случае оно обычно.берется по образу (выходам функции, т.е. по входам задачи обращения функции): см., например, [30, 1]. Отметим, что неизвестно, всегда ли полиномиально моделируемое распределение на выходах функции доминируется каким-либо распределением, индуцированным полиномиально моделируемым распределением на входах функции.

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

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

Метод основан на следующей простой идеи из доказательства Импа-льяццо [30, предложение 3] о получении полиномиального в среднем алгоритма из полиномиального алгоритма, который работает на доле входов (1 — ^г). Богданов и Тревисан используют эту идею для доказательства того, что из существования алгоритма для задачи об ограниченной остановке машины Тыоринга, который ошибается на доле входов вытекает, что все задачи из NP с полиномиально вычислимыми распределениями можно решить за полиномиальное в среднем время [11, предложение 3.5]. Идея состоит в том, что увеличение длины входа приводит к уменьшению вероятности ошибки. Этот метод адаптируется к задаче обращения функции. Однако рассматривается не конкретная функцию, а показывается, как модифицировать любую одностороннюю в среднем случае функцию, чтобы получить криптографически одностороннюю функцию для бесконечного

ХВ англоязычной литературе для этого понятия используется термин padding. числа длин входа.

Основным результатом главы 2 является следующая теорема.

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

Структурная теория сложности в среднем случае

Многие теоремы структурной теории сложности в наихудшем случае могут быть перенесены на сложность в среднем случае. Как уже упоминалось, были построены полные в среднем случае NP-задачи, показано что эти задачи обладают свойством самосводимости, построен аналог полиномиальной иерархии в среднем случае и пр. [38]. В главе 3 мы показываем, что некоторые структурные свойства сложностных классов, которые неизвестны в сложности в наихудшем случае, удастся доказать в сложности в среднем случае.

Основными структурными свойствами сложностных классов являются теорема об иерархии по времени (или памяти) и наличие полных задач. Класс сложности обычно определяется с помощью модели вычислений. Например, класс Р определяется полиномиальными по времени детерминированными машинами Тьюринга, класс NP — недетерминированными, а класс ВРР — вероятностными машинами Тыоринга, которые удовлетворяют условию ограниченной ошибки. Теорема об иерархии по времени утверждает, что данная модель вычислений может распознать строго больше языков за большее время. Полный язык — это «самый трудный» язык в классе, все остальные языки сводятся к нему.

На данный момент для класса ВРР неизвестно ни теоремы об иерархии по времени, ни полных задач относительно детерминированных сведений. Основное препятствие — это отсутствие вычислимой нумерации вероятностных машин, которые удовлетворяют условию ограниченной ошибки. Отметим, что если Р = ВРР, то класс ВРР содержит полный язык (подойдет любой язык из класса Р). Однако существует такой оракул А, что в классе ВРРЛ нет полных языков [26]. Из существования полной задачи в классе ВРР следует существование иерархии по времени (см., например, [7]). Лучший результат, связанный с иерархией по времени, суперполиномиальный: BPTime[n g п] С BPTime[2n ] [31]. Однако мы не можем доказать, что BPTime[n] С BPTime[n1001ogrV).

Прогресс в исследовании структурных свойств вероятностных классов сложности начался с теорем об иерархии по времени для вычислений с несколькими битами неравномерной подсказки [7, 17]. Последние результаты включают иерархии по времени для классов всего с одним битом подсказки: ВРР/1 [17], ZPP/1,MA/1 и др. [44]. Однако понятие подсказки, используемое в этих результатах, нестандартное, поскольку машины могут нарушать условие ограниченности ошибки, если подсказка неправильная. В случае, если использовать классическое определение подсказки, то существование иерархии по времени остается открытым вопросом, так как оно эквивалентно иерархии по времени без подсказки [18].

Другим результатом в этой области стало доказательство иерархии по времени для эвристических вероятностных алгоритмов с ограниченной ошибкой (эвристические алгоритмы могут ошибаться на маленькой доле входов). Иерархия по времени в классе HeurjBPP (с равномерным распределением) была доказана в [17], доказательство было существенно упрощено в [36]. Однако в этих результатах алгоритмы не только могут давать неверный ответ, но и нарушают условие ограниченности ошибки на малой доле входов. Возможность выдавать неверный ответ помогает и в построении полных объектов, например, существует полная криптосистема с открытым ключом, если декодирующий алгоритм может ошибаться с маленькой вероятностью [25] (см. также [22]).

В главе 3 мы рассматриваем класс AvgBPP [30], который состоит из распределенных задач, которые можно решить за полиномиальное в среднем случае время вероятностными алгоритмами с ограниченной ошибкой.

Мы строим язык С и полиномиально моделируемое распределение R, для которых доказываем следующую теорему:

Теорема 2. Задача (С, R) полна в классе (AvgBPP, PSamp) относительно детерминированных сведений по Тьюрингу.

Следствием этой теоремы является то, что если задача (С, R) принадлежит классу (AvgP, PSamp) (или даже (AvgjP, PSamp)), то (AvgBPP,PSamp) равняется (AvgP,PSamp). Аналогичное утверждение выполняется и для (HeurBPP, PSamp).

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

Теорема 3. Если существует полная задача в классе (AvgBPP, PSamp) относительно детерминированных сведений по Тьюрингу с плоским2 распределением, то для всех языков L е ВРЕХР распределенная задача (L, U) е AvgEXP, где AvgEXP — это множество распределенных задач, которые могут быть решены детерминированным алгоритмом за экспоненциальное в среднем случае время, a U обозначает равномерное распределение.

Мы доказываем теорему об иерархии по времени в классе (AvgBPP, PSamp).

Распределение называется плоским, если вероятность любой строки х не превосходит 2'х'е для некоторого е > 0.

Теорема 4. Для каждого с > 1 существует такой язык L и полиномиально моделируемое распределение Z), при котором (L, D) € AvgBPP и (L, Z?) ^ AvgBPTime[nc].

Мы сравниваем классы AvgP, AvgBPP, HeurP, HeurBPP с их аналогами в наихудшем случае и показываем, что включения строгие. В главе 3 доказана следующая теорема для детерминированных классов.

Теорема 5. Выполняются следующие соотношения:

1. (Р, U) С (AvgP, U) С (HeurP, U)\

2. (HeurP,PSamp) С (EXP,PSamp);

3. Существует такой язык Lexp £ EXP, что для любого распределения D £ PSamp задача (Lexp,D) не содержится в классе (HeurP, PSamp).

Также доказана аналогичная теорема для вероятностных классов. Теорема 6. Выполняются следующие соотношения

1. (ВРР,*7) С (AvgBPP, TJ) С (HeurBPP, XJ)\

2. (HeurBPP,PSamp) С (BPEXP,PSamp);

3. Существует такой язык L £ ВРЕХР, что для любого распределения D & PSamp задача (L, D) не содержится в классе (HeurBPP, PSamp).

Сложность обращения функции Голдрейха в среднем случае

В 2000-м году Голдрейх предложил функцию, основанную на графах-расширителях, и выдвинул гипотезу, что эта функция является односторонней [20]. Функция имеет п бинарных входов и п бинарных выходов.

Каждый выход функции зависит только от d входов и вычисляется по ним с помощью заданного d-местного предиката. Голдрейх предлагал использовать графы со свойством расширения в качестве графа зависимостей и случайный d-местный предикат. Функция, предложенная Голдрейхом, имеет некоторое сходство с псевдослучайным генератором Нисана-Вигдерсона [35].

Одним из практических подходов к обращению односторонних функций является использование современных программ, решающих задачу выполнимости булевой формулы [34]. Почти все реально используемые алгоритмы для задачи выполнимости булевой формулы основаны на методе расщепления (так называемые DPLL (по инициалам авторов Дэвис, Путнам, Логеман, Ловеленд) алгоритмы [14, 13]). Алгоритм расщепления — это рекурсивный алгоритм. При каждом вызове он упрощает входную формулу F (не влияя на ее выполнимость), выбирает переменную v из нее и делает два рекурсивных вызова на формулах F[v := 1] и F[v :— 0] в некотором порядке. Он отвечает «Выполнима», если по крайней мере один рекурсивный вызов отвечает то же самое (заметим, что нет необходимости делать второй вызов, если первый был удачный). Рекурсия продолжается, пока формула не станет тривиальной.

Алгоритм расщепления определяется правилами упрощения и двумя эвристиками: эвристика А выбирает переменную, а эвристика В выбирает, какое значение переменной будет проверено раньше.

Для невыполнимых формул нижние оценки на время работы алгоритмов расщепления следуют из нижних оценок на размер резолюционных доказательств [2]. Невыполнимые формулы, основанные на псевдослучайных генераторах Нисана-Вигдерсона, используются для доказательства нижних оценок в различных пропозициональных системах доказательств [4]. Но формулы, получающиеся из задач обращения односторонних функций, обычно являются выполнимыми. Вполне возможно, что расщепляющие алгоритмы быстро работают на выполнимых формулах. Если никак не ограничивать эвристики, то доказательство экспоненциальной нижней оценки на время работы расщепляющих алгоритмов на выполнимых формулах означало бы, что Р NP (иначе эвристика В могла бы за полиномиальное время вычислить правильное значение для переменной).

В работе [5] были получены безусловные экспоненциальные нижние оценки на время работы двух классов расщепляющих алгоритмов на выполнимых формулах. Первый класс алгоритмов — это «близорукие» алгоритмы. Эвристики в таких алгоритмах ограничены тем, что они могут прочитать лишь маленькую часть формулы точно, а остальную формулу они видят лишь схематично (например, как это сформулировано в [5], не видят знаков отрицания, но имеют доступ к числу вхождений переменной с положительным и отрицательным знаками). Для близоруких алгоритмов была получена экспоненциальная нижняя оценка для формул, кодирующих системы линейных уравнений, в которых матрица обладает свойством расширения. На самом деле, такие формулы кодируют функцию Голдрейха в случае линейного предиката. Второй класс алгоритмов расщепления, которые рассматривались в [5], — это «пьяные» алгоритмы. В таких алгоритмах эвристика выбора переменной ничем не ограничена и может быть даже невычислимой, а эвристика выбора значения, которое будет подставлено первым ограничена достаточно сильно: значение выбирается равновероятно случайным образом. Для «пьяных» алгоритмов нижняя оценка была построена для искусственных формул, которые строятся па основе трудных невыполнимых формул.

Функции Голдрейха, основанные на линейном предикате, не очень интересные, поскольку их эффективно можно обратить с помощью метода Гаусса. В работе [12] была обобщена техника, разработанная в [5] для доказательства нижней оценки для близоруких алгоритмов, на нелинейные предикаты. В частности, в [12] доказана экспоненциальная иижняя оценка на среднее (по входам функции) время обращения функции Голдрейха с предикатом х± фжг 0 • • • ®Xd-2 ®Xd-\Xd близорукими алгоритмами. Также в [12] был произведен практический анализ времени работы современных программ для задачи выполнимости булевой формулы, которые обращали функцию Голдрейха с этим предикатом, было показано, что эти формулы трудны для программы MiniSAT 2.0 [15, 16].

В работе [12] вопрос об экспоненциальных нижних оценках на время обращения функций Голдрейха «пьяными» алгоритмами оставлен открытым. В главе 2 мы отвечаем на этот вопрос. В частности, доказывается следующая теорема:

Теорема 7. Пусть Pd{x1: х2, ■ ■., xd) = ij©. xd-k © Q(xdk+ь .,xd), где Q — произвольный предикат, к + 1 < Для достаточно больших d и для достаточно больших п случайный двудольный граф G обладает с вероятностью хотя бы 0.85 следующим свойством. Для любого «пьяного» алгоритма А, Ргу<сгп{Рг{^( } > 2"(n)} > 1 - 2~п(п)} > 0.9, где д - это функция Голдрейха, построенная по предикату Pd и графу G, t^ обозначает время работы алгоритма Л на формуле Ф, а Фд(х)=ь — это формула в КНФ, кодирующая равенство д(х) = Ь.

План доказательства следующий: сначала мы доказываем нижнюю оценку для невыполнимых формул, пользуясь техникой из [9], затем показываем, что можно ввести некоторую надстройку над «пьяными» алгоритмами, которая лишь уменьшает время работы, но гарантирует, что в течении некоторого количества первых шагов алгоритм не обнаружит невыполнимого дизъюнкта. Далее мы покажем, что с большой вероятностью число выполняющих наборов у функции Голдрейха маленькое, и с большой вероятностью в результате работы надстройки текущая формула окажется невыполнимой, и можно будет применить нижнюю оценку для невыполнимых формул.

Общий план доказательства совпадает с планом, который был использован в [5] и [12], но получившееся доказательство существенно проще, чем в упомянутых выше статьях.

Мы также приводим доказательство экспоненциальной нижней оценки для «пьяных» алгоритмов в наихудшем случае. А именно, мы приводим простой способ построения трудной выполнимой формулы из любой невыполнимой формулы, трудной для метода резолюций. В частности, если использовать трудные невыполнимые формулы из статьи [37], то получается следующая теорема.

Теорема 8. Для каждого к > 3 существует положительная константа с^ = 0(/с-1/8), функция f(x) = и последовательность выполнимых формул Нп в (к + 1)-КНФ (Нп использует га переменных, где п < m < п2) такие, что время работы любого «пьяного» алгоритма на входе Нп меньше f'(n) с вероятностью не больше 2~п.

Структура диссертации

В главе 1 приводятся определения основных понятий, используемых в диссертации. В главе 2 устанавливается связь между существованием односторонних в среднем случае функций и бесконечно часто криптографически односторонних функций. В главе 3 изучаются структурные свойства класса AvgBPP. В главе 4 доказывается нижняя оценка на среднее время обращения функции Голдрейха «пьяными» алгоритмами.

Список литературы диссертационного исследования кандидат физико-математических наук Ицыксон, Дмитрий Михайлович, 2009 год

1. Левин J1. А. Односторонние функции // Проблемы передачи информации. 2003. Т. 39, № 1. С. 103-117.

2. Цейтии Г. С. О сложности вывода в исчислении высказываний // Записки научных семинаров ЛОМИ. 1968. Т. 8. С. 234-259.

3. Agrawal М., Kayal N., Saxena N. PRIMES is in P // Annals of Mathematics. 2002. Vol. 2. P. 781-793.

4. Alekhnovich M., Hirsch E. A., Itsykson D. Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas // Journal of Automating Reasoning. 2005. Vol. 35, N. 1-3. P. 51-72.

5. Babai L., Fortnow L., Nisan N., Wigderson A. BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs // Computational Complexity. 1993. Vol. 3. P. 307-318.

6. Barak B. A Probabilistic-Time Hierarchy Theorem for "Slightly Nonuniform" Algorithms // Proceedings of the 6th International Workshop on Randomization and Approximation Techniques (RANDOM '02). London, UK: Springer-Verlag, 2002. P. 194-208.

7. Ben-David S., Chor В., Goldreich 0., Luby M. On the theory of average case complexity // Journal of Computer and System Sciences. 1992. Vol. 44, N. 2. P. 193-219.

8. Ben-Sasson E., Wigderson A. Short proofs are narrow — resolution made simple // Journal of ACM. 2001. Vol. 48, N. 2. P. 149-169.

9. Blass A., Gurevich Y. Matrix Transformation is Complete for the Average Case // SIAM Journal on Computing. 1995. Vol. 24. P. 24-3.

10. Bogdanov A., Trevisan L. Average-Case Complexity // Foundation and Trends in Theoretical Computer Science. 2006. Vol. 2, N. 1. P. 1-106.

11. Cook J., Etesami O., Miller R., Trevisan L. Goldreich's One-Way Function Candidate and Myopic Backtracking Algorithms // Proceedings of the Sixth Theory of Cryptography Conference (TCC 2009). Springer-Verlag, 2009. P. 521-538.

12. Davis M., Logemann G., Loveland D. A machine program for theorem-proving // Communications of the ACM. 1962. Vol. 5. P. 394-397.

13. Davis M., Putnam H. A computing procedure for quantification theory // Journal of the ACM. 1960. Vol. 7. P. 201-215.

14. Een N., Biere A. Effective Preprocessing in SAT Through Variable and Clause Elimination // Theory and Applications of Satisfiability Testing. 2005. P. 61-75.

15. Fortnow L., Santhanam R. Hierarchy Theorems for Probabilistic Polynomial Time // Proceedings of the 45th Annual Symposium on Foundations of Computer Science (FOCS 2004). 2004. P. 316-324.

16. Fortnow L., Santhanam R. Time Hierarchies: A Survey: Tech. Rep. 07-004: Electronic Colloquium on Computational Complexity, 2007.

17. Gill J. Computational Complexity of Probabilistic Turing Machines // SIAM Journal on Computing. 1977. Vol. 6, N. 4. P. 675-695.

18. Goldreich 0. Candidate One-Way Functions Based on Expander Graphs: Tech. Rep. 00-090: Electronic Colloquium on Computational Complexity, 2000.

19. Goldreich O. Foundations of Cryptography. Cambridge University Press, 2001. Vol. 1.

20. Grigoriev D., Hirsch E. A., Pervyshev K. A Complete Public-Key Cryptosystem // Groups Complexity - Cryptology. 2009. Vol. 1, N. 1. P. 1-12.

21. Gurevich Y. Average Case Completeness // Journal of Computer and System Sciences. 1991. Vol. 42. P. 346-398.

22. Gurevich Y. Average Case Complexity // Proceedings of the 18th International Colloquium on Automata, Languages and Programming (ICALP '91). 1991. P. 615-628.

23. Hartmanis J., Hemachandra L. A. Complexity Classes Without Machines: On Complete Languages for UP // Proceedings of the 13th InternationalColloquium on Automata, Languages and Programming (ICALP '86). London, UK: Springer-Verlag, 1986. P. 123-135.

24. Hoory S., Linial N., Wigderson A. Expander Graphs and Their Applications j I Bulletin of the American Mathematical Society. 2006. Vol. 43. P. 439-561.

25. Impagliazzo R., Levin L. No better ways to generate hard NP instances than picking uniformly at random // Proceedings of the 31st IEEE Symposium on Foundations of Computer Science. 1990. P. 812-821.

26. Impagliazzo R., Shaltiel R., Wigderson A. Reducing The Seed Length In The Nisan-Wigderson Generator // Combinatorica. 2006. Vol. 26, N. 6. P. 647-681.

27. Impagliazzo R. A personal view of average-case complexity // Proceedings of the 10th Annual Structure in Complexity Theory Conference (SCT'95). Washington, DC, USA: IEEE Computer Society, 1995. P. 134.

28. Karpinski M., Verbeek R. Randomness, provability, and the separation of Monte Carlo time and space. London, UK: Springer-Verlag, 1987. P. 189207.

29. Levin L. Average case complete problems //■ SIAM Journal on Computing. 1986. Vol. 15, N. 1. P. 285-286.

30. McDiarmid C. Concentration. Springer-Verlag, 1998. Vol. 16 of Algorithms and Combinatorics. P. 195-248.

31. Nisan N., Wigderson A. Hardness vs. randomness // Journal of Computer and System Sciences. 1994. Vol. 49. P. 149-167.

32. Pervyshev K. On Heuristic Time Hierarchies // Proceedings of the IEEE Conference on Computational Complexity. 2007. P. 347-358.

33. Pudlak P., Impagliazzo R. A lower bound for DLL algorithms for k-SAT // Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00). 2000.

34. Schuler R., Yamakami T. Structural average case complexity // Journal of Computer and System Sciences. 1996. Vol. 52, N. 2. P. 308-327.

35. Shaltiel R., Umans C. Simple extractors for all min-entropies and a new pseudorandom generator // Journal of the ACM. 2005. Vol. 52, N. 2. P. 172-216.

36. Solovay R., Strassen V. A Fast Monte-Carlo Test for Primality // SIAM Journal on Computing. 1977. Vol. 6, N. 1. P. 84-85.

37. Sudan M., Trevisan L., Vadhan S. P. Pseudorandom Generators without the XOR Lemma // Journal of Computer and System Sciences. 2001. Vol. 62, N. 2. P. 236-266.

38. Umans C. Pseudo-random generators for all hardnesses // Journal of Computer and System Sciences. 2003. Vol. 67, N. 2. P. 419-440.

39. Urquhart A. Hard Examples for Resolution // Journal of the ACM. 1987. Vol. 34, N. 1. P. 209-219.44. van Melkebeek D., Pervyshev K. A Generic Time Hierarchy with One Bit of Advice 11 Computational Complexity. 2007. Vol. 16, N. 2. P. 139-179.