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

Оглавление
Введение 4
Сложность в среднем случае и криптография.................... 6
Структурная теория сложности в среднем случае............... 10
Сложность обращения функции Голдрейха в среднем случае ... 13
Структура диссертации....................................... 17
1 Основные понятия 18
1.1 Распределения на входах................................... 19
1.2 Полиномиальное в среднем случае время работы.............. 21
1.3 Классы распределенных задач поиска........................ 26
1.4 Классы распределенных задач распознавания ................ 27
1.5 Эвристические классы...................................... 28
1.6 Функции, односторонние для бесконечного числа длин входов 29
1.7 Функция Голдрейха......................................... 31
1.8 Алгоритмы расщепления .................................... 33
2 Бесконечно часто односторонние функции, основанные на
предположении о сложности в среднем случае 35
2.1 Сведения распределенных задач поиска...................... 36
2.2 Идея доказательства....................................... 37
2.3 Детали доказательства..................................... 39
3 Структурная сложность класса AvgBPP 44
3.1 Сведения распределенных задач распознавания .............. 44
2
3.2 Полная задача.............................................. 47
3.2.1 Основная идея....................................... 47
3.2.2 Детали конструкции.................................. 50
3.3 Полная задача с равномерным распределением и дерандомизация ......................................................... 57
3.4 Теорема об иерархии по времени............................. 58
3.5 Сложность із среднем и в наихудшем случае.................. 62
4 Нижняя оценка на среднее время обращения функции Гол-дрейха «пьяными» алгоритмами 67
4.1 Что можно эффективно решать «пьяными» алгоритмами? . 68
4.2 Алгоритмы расщепления и метод резолюций................... 71
4.3 Нижняя оценка для «пьяных» алгоритмов на выполнимых
формулах в наихудшем случае................................ 72
4.4 Поведение «пьяных» алгоритмов на невыполнимых формулах 76
4.5 Поведение «пьяных» алгоритмов на выполнимых формулах 78
4.5.1 Замыкание .......................................... 78
4.5.2 Надстройка над «пьяными» алгоритмами................ 80
4.5.3 Оценка числа решений................................ 85
4.5.4 Нижняя оценка времени работы........................ 88
3
Введение
Вероятностные алгоритмы с ограниченной ошибкой (также известные как алгоритмы Монте-Карло) — это алгоритмы, которые используют случайные числа и для каждого входа с вероятностью хотя бы 2 выдают правильный ответ. Интерес к вероятностным алгоритмам возрос в 1970-х годах, когда Соловэй и Штрассен опубликовали эффективный вероятностный алгоритм проверки числа на простоту [40]. Гилл [19] дал определение классу сложности ВРР, который состоит из языков, которые могут быть распознаны за полиномиальное время вероятностными алгоритмами с ограниченной ошибкой. Долгое время задача проверки числа на простоту была самым ярким примером задачи, для которой известен эффективный вероятностный алгоритмам, но не известен детерминированный. Однако в 2002 году появился детерминированный полиномиальный по времени тест числа на простоту |3]. На данный момент примером задачи, для которой известен эффективный вероятностный алгоритм, но не известен детерминированный, является задача проверки равенства нулю многочлена, записанного не обязательно в канонической форме.
Вопрос о совпадении классов сложности Р и ВРР является открытым. Результаты современных исследований о связи существования явных труд-иорешаемых задач и дерандомизации (35, б, 29, 41, 39, 42] дают основание для выдвижение гипотезы Р = ВРР (в частности, из существования булевой функции, которая вычислима за время 2сп, но не вычислима с помощью схем размера меньше, чем 2ГП, следует, что Р = ВРР).
Р и ВРР — это классы задач, которые можно эффективно решать на
4
практике. Для определения понятия надежности криптографического протокола нужно понимать, что значит, что задачу (взлом протокола) невозможно эффективно решать на практике. Из того, что задача не лежит в классе ВРР, еще не следует, что эту задачу нельзя эффективно решать на практике. Вполне возможно, что для каждой длины входа есть ровно один вход, для которого задача сложна, а для всех остальных входов задача является простой. Именно для нужд криптографии были сформулированы основные понятия теории сложности в среднем случае Левиным [32] и Гуревичем [23] в конце 1980-х годов.
В теории сложности в среднем случае массовые вычислительные задачи рассматриваются вместе с распределением на входах (индивидуальных задачах). Задачи, снабженные распределением, мы называем распределенными задачами. Мы рассматриваем полиномиально моделируемые распределения, т.е. такие, которые могут быть порождены за полиномиальное время с использованием равномерного распределения. Первое определение понятия полиномиального в среднем случае алгоритма дал Левин в [32]. Согласно Левину, алгоритм работает полиномиальное в среднем случае время, если существует такое положительное число б, что математическое ожидание функции Тс(х) по всем входам х длины п есть О (гг), где Т(х) — это время работы алгоритма на входе х. Эквивалентное определение дал Импальяццо в [30]; согласно ему, вычислительная задача решается за полиномиальное в среднем время, если для нее существует алгоритм с двумя параметрами х (вход) и 6 (вероятность ответа «не знаю»), время работы которого ограничено полиномом относительно ~ и который отвечает «не знаю» с вероятностью не больше 6 (в противном случае он выдает правильный ответ).
Левин |32] также доказал полноту в среднем случае задачи о замощении. Если задача о замощении может быть решена за полиномиальное в среднем время, то и все NP-зaдaчи с полиномиально моделируемыми распределениями могут быть решены за полиномиальное в среднем время.
5
Позже было доказано, что следующие распределенные задачи тоже являются полными в среднем случае: задача об ограниченной остановке машины Тьюринга, задача Поста [24], задача декомпозиции матрицы [10] и ДР.
Сложность в среднем случае и криптография
Пусть Е — конечный алфавит, мы рассматриваем функции, действующие из Еж в Е*. где Е* — это множество конечных слов в алфавите Е. Мы называем функцию / односторонней, если ее легко вычислить, но трудно обратить. Обычно принято считать, что функция легко вычислима, если она вычислима за полиномиальное время. Есть несколько подходов для определения трудности обращения функции.
• Односторонняя в наихудшем случае функция. Полиномиально вычислимая функция называется односторонней в наихудшем случае, если обратная функция не вычислима за полиномиальное время. Основной недостаток этого определения заключается в том, что трудных для обращения входов может быть очень мало и па самом деле функция может быть легко обращена на почти всех входах. Существование односторонних в наихудшем случае функций эквивалентно Р ^ ИР.
• Криптографшчсски од)юстороппяя (функция. Полиномиально вычислимая функция называется криптографически слабо односторонней, если для некоторой положительной константы с каждый вероятностный полиномиальный по времени алгоритм ошибается при обращении этой функции с вероятностью (по входам и случайным битам алгоритма) не мсиее для всех достаточно больших длин входов. Неизвестно никаких разумных предположений о сложностных классах, из которых следовало бы существование криптографически односторонних функций.
6
• Односторонняя о среднем случае функция.
Есть два способа определить трудность обращения функции на языке сложности в среднем случае.
1. Задача обращения функции / с полиномиально моделируемым распределением на входах / не решается никаким полиномиальным в среднем случае вероятностным алгоритмом с ограниченной ошибкой. В этом случае функцию / называют односторонней в среднем случае.
2. Задача обращения функции / с полиномиально моделируемым распределением на выходах (образах) / не решается никаким полиномиальным в среднем случае вероятностным алгоритмом с ограниченной ошибкой. В этом случае говорят, что задача обращения / — это трудная в среднем случае задача. Существование трудных в среднем случае задач эквивалентно ^Р,Р8атр) £ AvgBPP, где (ЫР,Р8атр) — это множество задач из НР с полиномиально моделируемыми распределениями, а А\щВРР — это множество распределенных задач, которые можно решить за полиномиальное в среднем время вероятностными алгоритмами с ограниченной ошибкой (этот факт следует из того, что любую распределенную задачу поиска из ИР с полиномиально моделируемым распределением можно свести к задаче поиска с равномерным распределением [28], а любую задачу поиска с равномерным распределением можно свести к некоторой задаче распознавания [8]).
Из существования односторонних в среднем случае функций следует существование трудных в среднем случае задач, поскольку полиномиально моделируемое распределение на входах функции порождает полиномиально моделируемое распределение на выходах функции.
Из существования криптографических односторонних функций следует существование односторонних в среднем функций (это простое следствие
7