Сложность в среднем случае вероятностных вычислений с ограниченной ошибкой

• Автор: Ицыксон, Дмитрий Михайлович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Санкт-Петербург
• Количество страниц: 93 с.

Оглавление
Введение
Сложность в среднем случае и криптография
Структурная теория сложности в среднем случае
Сложность обращения функции Голдрейха в среднем случае
Структура диссертации
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 году появился детерминированный полиномиальный по времени тест числа на простоту [3]. На данный момент примером задачи, для которой известен эффективный вероятностный алгоритм, но не известен детерминированный, является задача проверки равенства нулю многочлена, записанного не обязательно в канонической форме.
Вопрос о совпадении классов сложности Р и ВРР является открытым. Результаты современных исследований о связи существования явных труднорешаемых задач и дерандомизации [35, 6, 29, 41, 39, 42] дают основание для выдвижение гипотезы Р = ВРР (в частности, из существования булевой функции, которая вычислима за время 2е", но не вычислима с помощью схем размера меньше, чем 2е", следует, что Р = ВРР).
Р и ВРР — это классы задач, которые можно эффективно решать на

Глава
Бесконечно часто односторонние функции, основанные на предположении о сложности в среднем случае
Мы предполагаем существование вычислимой за полиномиальное время функции /, обратная к которой не вычислима вероятностным алгоритмом с ограниченной ошибкой за полиномиальное в среднем случае время. Криптографическое определение односторонней функции, однако, другое: даже для слабо односторонней функции успешный противник может не уметь обращать ее на полиномиальной доле входов. В этой главе мы показываем, как можно построить одностороннюю на бесконечной последовательности длин входов функцию, основанную на функции /.
В разделе 2.1 определяются сведения между распределенными задачами поиска и проверяется замкнутость классов FAvgP и FAvgBPP относительно этих сведений. В разделе 2.2 приводится основная идея кон-