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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

Ицыксои Дмитрий Михайлович

□□3487704

СЛОЖНОСТЬ В СРЕДНЕМ СЛУЧАЕ ВЕРОЯТНОСТНЫХ ВЫЧИСЛЕНИЙ С ОГРАНИЧЕННОЙ ОШИБКОЙ

01.01.06 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 о ДЕК 2009

Санкт-Петербург

2009

003487704

Работа выполнена в лаборатории математической логики Учреждения Российской академии наук Санкт-Петербургского отделения Математического института им. В. А. Стеклова РАН

Научный руководитель: кандидат физико-математических наук,

доцент Гирш Эдуард Алексеевич Официальные оппоненты: доктор физико-математических паук,

па заседании совета Д 212.232.29 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 191023, Санкт-Петербург, наб. р. Фонтанки, 27, ауд. 311 (помещение ПОМИ РАН).

Адрес диссертационного совета: 198504, Санкт-Петербург, Ст. Петергоф, Университетский пр. д. 28.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан /-(СхУ^рл 2009 г.

Ученый секретарь диссертационного совета,

профессор Верещагин Николай Константинович (Московский государственный университет имени М.В. Ломоносова) кандидат физико-математических наук Вяткипа Кира Вадимовна (Санкт-Петербургский государственный университет)

Ведущая организация: Вычислительный центр

им. А. А. Дородницына РАН Защита диссертации состоится 2009 г. в //-

час.

доктор физ.-мат. паук, профессор

Нежинский В. М.

Общая характеристика работы

Актуальность темы. Интерес к вероятностным алгоритмам с огра-ничеппой ошибкой возрос н 1970-х годах, когда Соловэй и Штрассен опубликовали эффективный вероятностный алгоритм проверки числа па простоту. В те же годы Гилл дал определение классу сложности ВРР, состоящему из языков, которые могут быть распознаны за полиномиальное время вероятностными алгоритмами с ограниченной ошибкой. Долгое время задача проверки числа па простоту была самым ярким примером задачи, которая эффективно решается вероятностными алгоритмами, но не решается детерминированными. Однако в 2002 году Агравал, Каял и Сакссна предложили детерминированный полиномиальный но времени тест числа на простоту.

Неизвестно, совпадают ли классы Р и ВРР. Полиномиальный алгоритм проверки числа па простоту и результаты современных исследований о связи существования явных труднорешаемых задач и дерандомизации (работы Нисана, Вигдерсопа и др. 1994-2003 гг.) дают основание для выдвижения гипотезы Р = ВРР (в частности, из существования булевой функции, которая вычислима за время 2е", по не вычислима с помощью схем размера меньше, чем 2е", следует, что Р = ВРР).

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

В теории сложности в среднем случае массовые вычислительные за-

дачи рассматриваются имеете с распределением па »ходах (индивидуальных задачах). Задачи, снабженные распределением, мы называем распределенными задачами. Мы рассматриваем полиномиально моделируемые распределения, т.е. такие, которые могут быть порождены за полиномиальное время с использованием равномерного распределения. Первое определение понятия полиномиального в среднем случае алгоритма дал Левин в 1986 году. Левин также доказал полноту в среднем случае задачи о замощении. Если задача о замощении может быть решена за полиномиальное о среднем время, то и нее NP-зaдaчи с полиномиально моделируемыми распределениями могут быть решены за полииомиальпос в среднем время. Позже было доказано, что следующие распределенные задачи тоже являются полными в среднем случае: задача об ограниченной остановке машины Тыорипга, задача Поста (Гурсвич, 1991), задача декомпозиции матрицы (Басс, Гуревич, 1905) и др.

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

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

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

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

Если задача обращении функции / с полиномиально моделируемым распределением па выходах (образах) / не решается никаким полиномиальным и среднем случае иероятностным алгоритмом с ограниченной ошибкой, то говорят, что задача обращения / — это трудная в среднем случае задача. Существование трудных в среднем случае задач эквивалентно ^Р,Р8атр) % AvgBPP, где (КР.РБатр) — это множество задач из КР с полиномиально моделируемыми распределениями, aAvgBPP — это множество распределенных задач, решаемых за полиномиальное в среднем время вероятностными алгоритмами с ограниченной ошибкой.

Из существования односторонних в среднем случае функций следует существование трудных в среднем случае задач, поскольку полиномиально моделируемое распределение па входах функции порождает полиномиально моделируемое распределение на выходах функции. Из существования криптографических односторонних функций следует существование односторонних в среднем функций, из чего следует существование трудных в среднем задач, что влечет (КР,Р8атр) % AvgBPP. Следует ли из (КР,Р8атр) <2 Ау§ВРР существование криптографических односторонних функций, является важнейшим открытым вопросом. Следует ли из ^Р,Р8атр) £ AvgBPP существование односторонних I! среднем случае функций, также является открытым вопросом. Можно показать (Левин, 2003), что если существует трудная в среднем задача обращения функции, сохраняющей длину, с равномерным распределением, то существует и односторонняя в среднем функция (эти два условия столь сильные, что их не получается удовлетворить, основываясь ни па одной из известных полных задач в классе (КР,Р8атр)).

На данный момент для класса ВРР неизвестно ни теоремы об иерархии по времени, ни полных задач относительно детерминированных сведе-

пий. Основное препятствие — это отсутствие вычислимой нумерации вероятностных машин, которые удовлетворяют условию ограниченной ошибки. Отметим, что если Р = ВРР, то класс ВРР содержит полный язык (подойдет любой язык из класс Р). Однако существует такой оракул А, что в классе ВРР'4 пет полных языков (Хартмапис, Хемачапдра, 1986). Из существования полной задачи в классе ВРР следует существование, иерархии по времени (Барак, 2002). Лучший результат, связанный с иерархией по времени, супернолиномиальный: BPTime[n'°s"] С BPTime[2"'] (Карпинский, Вербек, 1987). Однако, мы не можем доказать, например, что BPTime[n] С BPTime[n1001ogn].

Первый прогресс в исследовании структурных свойств вероятностных классов сложности — это теорема об иерархии по времени для вычислений с несколькими битами неравномерной подсказки (Барак, 2002; Фортноу, Сапсанам, 2004), последние результаты включают иерархию по времени для классов всего с одним битом подсказки: ВРР/1 (Фортноу, Сапсанам, 2004), ZPP/1.MA/1 и т.д. (Мелкебск, Первышев, 2007). Однако, понятие подсказки, используемое в этих результатах нестандартное, поскольку машины могут нарушать условие ограниченности ошибки, если подсказка неправильная. В случае, если использовать классическое определение подсказки, то существование иерархии по времени остается открытым вопросом, так как оно эквивалентно иерархии по времени без иод-сказки. Другим результатом в этой области стало доказательство иерархии по времени для эвристических вероятностных алгоритмов с ограниченной ошибкой (эвристические алгоритмы могут ошибаться на маленькой доле входов). Иерархия rio времени в классе Heurj_BPP (с равномерным распределением) была доказана в (Фортноу, Сапсанам, 2004), доказательство было существенно упрощено в (Первышев, 2007). Однако, в этих результатах алгоритмы не только могут давать неверный ответ, по и нарушают условие ограниченности ошибки на малой доле входов. Возможность выдавать неверный ответ помогает и в построении полных объектов, например, существует полная криптосистема с открытым ключом, если декодирую-

щий алгоритм может ошибаться с маленькой вероятностью (Хариик и др., 2005).

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

Одним из практических подходов к обращению односторонних функций является использование современных программ, решающих задачу выполнимости булевой формулы. Практически все реально используемые алгоритмы для задачи выполнимости булевой формулы основаны па методе расщепления (по инициалам авторов (Дэвис, Путнам, 1960), (Дэвис, Логе-ман, Ловеленд, 1962) такие алгоритмы называют ОРЬЬ алгоритмами).

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

В работе (Дж. Кук и др., 2009) изучается сложность обращения функции Голдрейха, основанной на предикате х\ © Х2 Ф ■ • • © х,1-2 ® х,1-гх(1- Для

«близор.уких» алгоритмов, основанных па расщеплении доказывается экспоненциальная нижняя оценка па среднюю сложность обращения таких функций. В «близоруких» алгоритмах эвристики выбора переменной и выбора значения, которое будет рассматриваться первым, в таких алгоритмах ограничены тем, что они могут за каждый шаг прочитать лишь маленькую часть строки, на которой функция обращается. Также было показано, что задача обращения функции Голдройхаетаким предикатом трудна для программ MiniSAT 2.0. Вопрос о экспоненциальных нижних оценках па время обращения функций Голдрейха «пьяными» алгоритмами оставлен открытым в (Дж. Кук и др., 2009). В классе «пьяных» алгоритмов эвристика выбора переменной ничем не ограничена и может быть даже невычислимой, а эвристика выбора значения, которое будет подставлено первым, ограничено достаточно сильно: значение выбирается равновероятно случайным образом.

Цели работы.

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

2. Построить распределенную задачу, которая является полной в классе (AvgBPP, PSamp) относительно детерминированных сведений.

3. Доказать теорему об иерархии по времени в классе (AvgBPP, PSamp).

4. Сравнить класс сложности AvgP с классами Р и ЕХР, сравнить класс AvgBPP с классами ВРР и ВРЕХР.

5. Построить трудные выполнимые формулы для «пьяных» алгоритмов, которые основаны на трудных невыполнимых формулах.

6. Получить нижнюю оценку на среднее время обращения функции Голдрейха, основанной на нелинейном предикате, «пьяными» алгоритмами.

Общая методика работы. В работе используются методы теории сложности вычислений. Для доказательства нижней оценки па среднее время обращения функции Голдрейха используются методы теории сложности доказательств и техника работы с графами-расширителями. Основные результаты.

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

2. Построена распределенная задача, которая является полной в классе (AvgBPP, PSamp).

3. Доказана теорема об иерархии но времени в классе (AvgBPP, PSamp).

4. Доказаны включения (для полиномиально моделируемых распределений): Р С AvgP С HeurP С ЕХР и ВРР С AvgBPP С HeurBPP С ВРЕХР.

5. Построены трудные выполнимые формулы для «пьяных» алгоритмов, которые основаны па трудных невыполнимых формулах.

6. Доказана нижняя оценка на среднее время обращения функции Голдрейха «пьяными» алгоритмами, где функция Голдрейха основана на случайном графе и предикате Х\ © ... x,i-k © Qi^d-k+i ■ ■ ■ xd)> к+ \ <'\,&Q — произвольный предикат.

Научная новизна. Все результаты, представленные в диссертации, являются новыми.

Практическая и теоретическая ценность. Работа носит теоретический характер. Результаты работы могут быть использованы для из.у-

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

Апробация работы. Основные результаты были доложены на следующих конференциях и семинарах: международная конференция International Colloquium 011 Automata, Languages and Programming (ICALP 2004), Финляндия, 2004; международная школа Estonian Winter School in Computer Science (EWSCS 2005), Эстония, 2005; международная конференция Workshop on Computationai, Dcscriptive and Proof Complexity, and Algorithms, Россия, 2007; международная конференция Workshop on Logic, Language, Information and Computation (WoLLIC 2008), Великобритания, 2008; международная школа Estonian Winter School in Computer Science (EWSCS 2009), Эстония, 2009; российско-австрийский семинар Логика конечного и бесконечного, Австрия, 2009; международный симпозиум International Computer Science Symposium in Russia (CSR 2009), Россия, 2009.

Результаты, лежащие в основе диссертации, неоднократно докладывались на семинаре ПОМИ РАН. Два доклада были признаны лучшими па студенческих школах EWSCS 2005 и EWSCS 2009. Работа, содержащая результаты диссертации, удостоена третьей премии в номинации «аспиранты» па конкурсе молодых математиков Фонда Эйлера. Статья па конференции CSR 2009 получила премию за лучшую студенческую статью.

Публикации результатов. Основные результаты диссертации опубликованы в пяти работах [1-5]. В работах [1, 4] соискателю принадлежит доказательство того, что при модификации с помощью наполнителя функция, которая не обращается за полиномиальное в среднем случае время, превращается в криптографически одностороннюю. Конструкция модификации с помощью наполнителя получена совместно с Э. А. Гиршем. В работе [2] соискателю принадлежит доказательство экспоненциальной нижней оценки на время работы «пьяных» алгоритмов па выполнимых формулах, доказательство нижней оценки для «близоруких» алгоритмов

принадлежит соавторам. Работы [1,2] опубликованы н изданиях, входящих в список рекомендованных Высшей аттестационной комиссией.

Структура и объем диссертации. Диссертация объемом 93 страницы состоит из »ведения и четырех основных глав, разбитых на разделы и подразделы. Список цитируемой литературы состоит из 44 наименований.

Содержание работы

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

В первой главе даются определения основных понятий, используемых в диссертации. В первом разделе даны определения ансамбля распределений и распределенных задач распознавания и распредсленпыхКР-задач поиска. Во втором разделе даны определения того, что значит, что алгоритм работает полиномиальное в среднем время по Левину и по Им-пальяццо. Для вероятностных алгоритмов с ограниченной ошибкой приведено доказательство эквивалентности этих определений.

Согласно Левину, алгоритм работает полиномиальное 15 среднем случае время, если существует такое положительное число е, что математическое ожидание функции Те(х) по всем входам х длины п есть 0(п), где Т{х) — это время работы алгоритма на входе х. Эквивалентное определение дал Импальяццо в 1995 году; согласно ему, вычислительная задача решается за полиномиальное в среднем время, если для нее существует алгоритм с двумя параметрами х (вход) и 6 (вероятность ответа «не знаю»), время работы которого ограничено полиномом относительно^ и который отвечает «не знаю» с вероятностью по больше 6 (в противном случае он выдаст правильный ответ).

В третьем разделе даны определения классов распределенных задач поиска FAvgP и FAvgBPP. В четвертом разделе даны определения классов распределенных задач распозпо-вания AvgP, AvgBPP, Ау§Л(п)Р, Avgí(„)BPP, АудТипе^п)],

АуцВРТипе[д(п)! и AvgEXP. В пятом разделе даны определения эвристических классов задач распознавания: НеигР, НеигВРР, Неиг5(п)Р, Неигг(п)ВРР, НеигТ1те[д(п)], НеигВРТнпе[д(п)],

Ау§6(п)ВРТипе[д(п)], Неиг6(п)РТ1те[д(п)], Неиг^ВРТнпе^п)]. В шестом разделе дано определение функций, криптографически односторонних для бесконечного числа длин входов. В седьмом разделе даны определения функции Голдрейха и двудольного граничного графа-расширителя, приведена теорема о существовании нужных графов-расширителей. В восьмом разделе приведено общее определение алгоритмов расщепления и дано определение «пьяных» алгоритмов расщепления.

Во второй главе приведен результат, показывающий, как из полиномиально вычислимой функции, которую не обратить полиномиальным в среднем вероятностным алгоритмом с ограниченной ошибкой, построить функцию, которая будет криптографически односторонней для бесконечного числа длин входов. В первом разделе приводятся детерминированные сведения «многие к одному» между распределенными задачами поиска и доказывается замкнутость классовFAvgBPP и ГАу§Р относительно этих сведений. Во втором разделе показывается, почему односторонняя в среднем случае функция не является автоматически слабой односторонней функцией, и приводится основная идея конструкции. Основная идея доказательства заключается в том, чтобы снабдить исходную функцию наполнителем. А именно, определяется новая функция /р{х,у) на парах строк, которая применяет / к своему первому аргументу и заменяет второй аргумент на строку В третьем разделе приводится конструкция со всеми деталями и доказывается теорема:

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

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

В третьей главе изучается структурные свойства класса AvgBPP. В первом разделе приводятся определения безошибочных и эвристических детерминированных сведений по Тыорипгу и доказывается замкнутость класса AvgP относительно безошибочных сведений и НеигР относительно эвристических сведений. Во втором разделе строится язык С и полиномиально моделируемое распределение Д, для которых доказывается следующая теорема:

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

Следствием этой теоремы является то, что если задача [С, К) принадлежит классу (AvgP,PSamp) (или даже (Avg^rP,РБатр)), то (AvgBPP, РБатр) равняется (AvgP, РБатр). Аналогичное утверждение выполняется и для (НеигВРР, РБатр).

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

Теорема 3. Если существует полная задача в классе (AvgBPP, РЭатр) относительно детерминированных сведений по Тьюрингу с плоским1 распределением, то для всех языков Ь € ВРЕХР распределенная задача (Ь, {/) решается детерминированным алгоритмом с экспоненциальным в среднем случае временем, где и обозначает равномерное распределение.

В четвертом параграфе доказывается теорема об иерархии по времени в классе (AvgBPP, РБатр).

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

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

В пятом параграфе сравниваются классы

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

Теорема 5. Выполняются следующие соотношения: 1) (Р,[/) С (AvgP, U) С (HeurP, U); 2) (HeurP,PSamp) С (EXP,PSamp); 3)

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

Также доказывается аналогичная теорема для вероятностных классов:

Теорема 6. Выполняются следующие соотношения 1) (ВРР,[/) С (AvgBPP, С) С (HeurBPP, U); 2) (HeurBPP, PSamp) С (ВРЕХР, PSamp); 3) Существует язык L 6 ВРРЕХР, что для любого распределения D 6 PSamp задача (L, D) не содержится в классе (HeurBPP, PSamp).

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

Предложение 1. Время работы «пьяного» алгоритма па невыполнимой формуле не меньше, чем размер (количество дизъюнктов) кратчайшего древовидного революционного доказательства.

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

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

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

В пятом разделе доказывается основной результат: экспоненциальная нижняя оценка па время обращения функции Голдрейха «пьяными» алгоритмами в среднем случае. В первом подразделе приводятся определения ¿-замыкания и множества С1к и доказывается оценка па размер /с-замыкапия. Во втором подразделе приводится описание надстройки над «пьяными» алгоритмами, которая не увеличивает время работы «пьяного» алгоритма на формулах, кодирующих задачу обращения функции Голдрейха, при которой алгоритм в течение линейного числа подстановок не совершает возвратов. В третьем подразделе оценивается количество решений уравнения д(х) = д(у) для функции Голдрейха д, построенной по случайному графу. В четвертом подразделе доказывается основная теорема:

Теорема 8. Пусть Р,1{хих2,... ,х(1) = х\ 8 ... хЛ-к 0 (2{х(1-к+1, ■ ■ ■ ,£<()> где <5 ~ произвольный предикат, к + 1 < Для достаточно больших й

и для достаточно больших п случайный двудольный граф G обладает с вероятностью хотя бы 0.85 следующим свойством: для любого «пьяного» алгоритма Л, Рг,,_£/ {Pr{t$ > 2"(н)} > 1 - 2~и(-п)] > 0.9, где g — это функция Голдрейха, построенная по предикату Ра и графу G, t\¡> обозначает время работы алгоритма А на формуле Ф, а Фя(ж)=(, — это формула в КНФ, кодирующая равенство д(х) = Ь.

Публикации автора по теме диссертации Статьи в журналах, рекомендованных ВАК:

1. Гирш Э.А., Ицыксон Д.М. Бесконечно часто односторонняя функция, основанная па предположении о сложности в среднем // Алгебра и Анализ. 2009. Том 21, № 3. С. 130-144.

2. Alckhnovich М., Hirsch Е. A., Itsykson D. Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiablc Formulas // Journal of Automated Reasoning. 2005. Vol. 35, N. 1-3. P. 51-72.

Другие публикации:

3. Ицыксон Д.М. Нижняя оценка на среднее время обращения функции Голдрейха «пьяными» алгоритмами расщепления // Препринты ПОМИ РАН. 2009. № 3. С. 1-17.

4. Hirsch Е. A., Itsykson D. М. An infinitcly-oftcn one-way function based on an average-case assumption // Proceedings of the 15th Workshop on Logic, Language, Information and Computation. Vol. 5110 of Lecture Notes in Computer Science. 2008. P. 208- 217.

5. Itsykson D. M. Structural complexity of AvgBPP // Proceedings of the 4th International Computer Science Symposium in Russia, LNCS. Vol. 5675 of Lecture Notes in Computer Science. 2009. P. 155-166.

Подписано в печать 16.10.2009. Формат 60X84 1/16. Печать цифровая. Усл. печ. л. 1,0. Уч.-изд. л. 1,0. Тираж 100. Заказ 25 .

Отпечатано с готового оригинал-макета, предоставленного автором, в центре оперативной полиграфии факультета технической кибернетики СПбГПУ. 195251, Санкт-Петербург, Политехническая ул., 21 Тел.: (812) 297-70-43

Введение

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

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

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

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

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 доказывается нижняя оценка на среднее время обращения функции Голдрейха «пьяными» алгоритмами.

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.