Сложность эвристических вычислений и интерактивных протоколов Кноп Александр Анатольевич

Содержание к диссертации

Введение

Цели, полученные результаты и структура диссертации 11

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

1.1 Классы эвристических вычислений 17

1.2 Классы распределений 20

2 Схемная сложность AvgMA 22

2.1 Определения 23

2.2 Эвристические сведения 24

2.3 Нижние оценки 25

2.4 HeurAM, HeurNP и препятствия к доказательству нижних оценок 30

3 Иерархии относительно сложности языков 36

3.1 Основные определения и обозначения 37

3.2 Иерархия для HeurBPP 37

3.3 Условные иерархии для BPP 39

3.4 Теорема об иерархии для функций 40

3.5 Иерархия с произвольными распределениями 42

3.6 Иерархия для HeurNP 43

4 Иерархии относительно сложности распределений 47

4.1 Основные определения и обозначения 47

4.2 Сэмплируемые распределения

4.2.1 Строгая сложность 48

4.2.2 Слабая сложность 56

4.3 Вычислимые распределения 62

Заключение 64

Литература

• Классы распределений
• Эвристические сведения
• Иерархия для HeurBPP
• Строгая сложность

Введение к работе

Актуальность темы

В классической теории сложности рассматривается время работы алгоритма (интерактивного протокола) в наихудшем случае. Однако для приложений, как правило, интереснее среднее время работы. В связи с этим в 1986 году Левин начал исследования в на тот момент новом разделе теории сложности — теории сложности в среднем.

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

1. насколько ресурс «время работы» существенен, правда ли, что за большее время можно решить большее число задач, и если да, то насколько;

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

В терминах структурной сложности эти вопросы можно сформулировать следующим образом:

3. для каких моделей вычислений C верно, что для любого выполняется условие CP CTime[], то есть полиномиальные по времени вычисления не моделируются за время ;

4. для каких моделей вычислений C верно, что для любого выполняется условие CP Size[], то есть полиномиальные по времени вычисления не моделируются вычислениями при помощи булевых схем размера .

В классическом случае оба этих вопроса решены не полностью. Исследование первого из них началось в 1967 году с работы Хартманиса и Стернса в

которой они доказали, что Р ^ DTime[n^fc] для любого к. Для доказательства этого результата ими была использована техника диагонализации. Однако этот метод невозможно перенести на классы, не замкнутые относительно отрицания, такие как NP. Для этих классов вопрос о существовании иерархии оставался открытым, пока в 1973 году Кук не доказал, что NP ^ NTime[n^fc] для всех к. Его доказательство базировалось на существовании NP-полной задачи и на иерархии для детерминированных вычислений. К сожалению, доказательство было сложным и не переносилось на другие классы. Десять лет спустя, в 1983 году, Зак предложил новое, более простое, доказательство, основанное на отложенной диагонализации. Это доказательство позволило доказать иерархию для всех синтаксических моделей вычислений, но для семантических же моделей, таких как ВРР, вопрос до сих пор открыт. В 2004 году Фортноу и Сантанам совершили прорыв и доказали иерархию по времени для эвристических вероятностных алгоритмов с ограниченной ошибкой (они доказали, что Heur^BPP ^ Heur^BPTimefn^]), для доказательства этого факта они воспользовались существованием оптимального алгоритма для PSpace-полного языка, их доказательство было технически сложным и не переносилось на другие модели вычислений. В 2007 году Первышев улучшил этот результат, доказав, что Heur^BPP ^ Heuri.^BPTimefn^] для всех /с, и

разработав технику, позволяющую доказать теоремы об иерархии для других семантических моделей вычислений (таких как интерактивные протоколы). В то же время вопрос об увеличении параметра ошибки выше ^ — 5 все еще открыт.

Исследования второго вопроса начались в 1982 году с работы Канна-на, в которой он доказал, что S2P ^ Size[n^fc] для всех к. Доказательство базировалось на теореме Карпа-Липтона. В 2001 Кай заметил, что теорему Карпа-Липтона можно усилить и тем самым доказать, что S2P ^ Size[n^fc] для любого к. К сожалению, успехи в классическом случае на этом закончи-

лись. Однако в 2009 Сантанам доказал, что MA/1 ^ Size[n^k], тем самым улучшив предыдущие результаты.

Во всех вышеупомянутых результатах среднее время работы считалось по равномерному распределению, но естественно было бы рассматривать и другие распределения. Однако, если не ограничивать никак класс распределений, то становятся верны несколько парадоксальные утверждения: так, в 1992 году Ли и Витани доказали, что существует такое распределение D, что (L, D) Є Heur і Р тогда и только тогда, когда L Є Р. В связи с этим, как пра-вило, рассматривают распределения из какого-нибудь естественного класса. Своеобразным аналогом вопроса об иерархии по времени является следующий вопрос: может ли усложнение распределения увеличить сложность языка и, наоборот, можно ли уменьшить сложность языка, увеличив сложность распределения. В 1987 году Гуревич и Шелах доказали, что существует алгоритм, который проверяет граф на гамильтоновость за линейное время в среднем на равномерном распределении, что косвенно указывает на возможность положительного ответа на этот вопрос.

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

Степень разработанности темы

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

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

момент лучшим результатом в этой области является З.ОІп — о{п) (оценку можно улучшить до Ъп — о(п), если рассматривать схемы в базисе де Моргана). Другим вариантом является исследование ограниченных классов схем. Это направление оказывается более успешным, известна экспоненциальная нижняя оценка на монотонную схемную сложность, а также на схемы с ограниченной глубиной. Однако и это направление не привело к успехам в общем случае.

Последнее направление — это попытки доказать нижние оценки для функций из все меньших и меньших классов. Экспоненциальная нижняя оценка, полученная подсчетом, требует дважды экспоненциального времени. Бурман и другие показали, что данную оценку можно усилить и найти функцию экспоненциальной сложности в классе МАехр. Менее амбициозной целью является доказательство нижних оценок вида п^к (для всех к). Это направление исследований было начато Кананом, который показал, что для каждого к существует язык из S2P П П2Р, не имеющий схем размера п^к. Данный результат был усилен до языков из класса S2P. При этом попытки доказать существование такого языка в классе МА не привели ни к чему лучше задач из PromiseNLA и языков из МА/1 (утверждение было доказано при помощи техники, разработанной в работах Барака, Фортноу и Сантанама).

Препятствие на пути доказательства нижних оценок на языки из МА типично для результатов структурной теории сложности (таких как иерархии по времени, существование полной задачи) для семантических классов. В конструкции Сантанама протокол не на всех входах имеет ограниченную вероятность ошибки, требующуюся в определении класса МА. Аналогичную проблему решил Первышев для теоремы об иерархии по времени в классе эвристических вероятностных алгоритмов с ограниченной ошибкой; ее же решил Ицыксон при построении AvgBPP-полной задачи (вопрос существо-

вания AvgMA-полной задачи все еще открыт). Они решили эту проблему, сопоставив каждому входу вероятность, начиная с которой мы примем данный вход.

Вопрос 1. Можно ли доказать нижнюю оценку на эвристическую схемную сложность задачи из эвристического аналога класса МА?

Теоремы об иерархиях по времени. Теорема об иерархии по времени для некоторой модели вычислений утверждает, что в данной модели вычислений за большее время можно решить строго большее множество задач. Для детерминированных машин Тьюринга подобная теорема была доказана Хартманисом и Стернсом при помощи диагонализации. Для того чтобы показать, что существует язык, разрешимый за 0(п^) шагов, но не разрешимый за п² шагов, можно рассмотреть язык, содержащий строку х тогда и только тогда, когда машина Тьюринга М_х отвергает х за п² шагов. Иерархии по времени известны для всех синтаксических моделей вычислений. При этом стандартная диагонализация не работает, если класс не замкнут относительно дополнения (как, например, NP). Однако отложенная диагонализация, предложенная Заком, работает для всех синтаксических моделей.

Вычислительная модель называется семантической, если невозможно эффективно перечислить все корректные машины. Например, BPTime, RTime и ZPTime являются семантическими. На текущий момент неизвестно никаких точных теорем об иерархии по времени для семантических моделей вычислений. Например, лучший результат об иерархии по времени для вероятностных вычислений с ограниченной ошибкой имеет суперполиномиальный зазор: BPTime[n^logn] С BPTime[2ⁿ].

Первым продвижением в данной теме была теорема об иерархии по времени для вероятностных вычислений с несколькими битами неравномерной подсказки, позже была доказана иерархия для всех семантических классов с

одним битом подсказки: BPTime/1, ZPTime/1, MATime/1 и т.д.

Фортноу и Сантанам также доказали иерархию по времени для эвристических вероятностных алгоритмов с ограниченной ошибкой (такие алгоритмы могут на «малой» доле входов выдавать неправильный ответ или выдавать ответ с неправильной вероятностью). Точнее, они показали, что существует язык L, такой, что {L,U) принадлежит Heurj_BPP, но {L,U)

п^с

не принадлежит Heiirj_BPTime[n^a]. Доказательство этого факта также ба-

п^с

зируется на существовании оптимального алгоритма для PSpace-полного языка. Первышев упростил и усилил данную теорему об иерархии для эвристической версии BPTime, он доказал, что существует язык L, такой, что (L,U) Є Heur_eBPP, но (L,U) ^ Heiiri__eBPTime[n^a]. Первышев ис-пользовал отложенную диагонализацию против всех вероятностных машин. Отложенная диагонализация требует возможности промоделировать машину на входах с длиной, большей на единицу. Проблема заключается в том, что вероятностная машина может принять вход с произвольной вероятностью, поэтому промоделировать такую машину невозможно при помощи машин с ограниченной ошибкой. Пусть М — это вероятностная машина Тьюринга, которая не соблюдает условие ограниченной ошибки, но нам необходимо промоделировать ее на входе х. Первышев придумал метод, как промоделировать машину эвристически: для каждого входа х мы рассматриваем множество строк {г/і, 2/2, iVn}, где N достаточно большое. Для каждой строки у і запускаем М(х) много раз и вычисляем долю единиц щ среди ответов М(х). Алгоритм принимает у,, если щ больше в_Уі, где в_у. = ^ + ^. Заметим, что если М(х) выполняет условие ограниченной ошибки, то с высокой вероятностью ответы для всех у і будет одинаковыми. А если М(х) не соблюдает условие ограниченной ошибки, то наш алгоритм не соблюдает его только на малой доле строк у^ точнее, на таких у^ что в_у. очень близка к Рт[М(х) = 1].

Вопрос 2. Можно ли доказать иерархию по времени для эвристических вы-

числений с параметром ошибки 1 - вместо ¹₂ - ?

Несложно заметить, что данное доказательство можно переделать в доказательство того, что существует такое полиномиально сэмплируемое распределение, что любое распределение, сэмплируемое за время , имеет статистическое расстояние с ним не меньше ¹₂ - . В 2013 году Ватсон улучшил этот результат и доказал, что для любых констант и существует такое PSamp, что носитель лежит в [], и для любого DSamp[] для бесконечно многих статистическое расстояние между и не меньше 1 - ¹ - .

Вопрос 3. Можно ли формализовать связь между теоремой Ватсона и иерархиями по времени для эвристических распределений?

Иерархии относительно сложности распределений. Как уже было сказано ранее, в теории сложности в среднем рассматриваются задачи в паре с распределением на входах. Задача называется простой в среднем, если она может быть эффективно решена на большой относительно этого распределения доле входов.

Соответственно, вопрос о том, как связана сложность проблемы с распределением на входах, естественен. Известно, что многие трудные задачи можно решить за полиномиальное в среднем время на равномерном распределении на входах: такое доказано для проверки графа на гамильтоновость (заметим, что в классическом случае данная задача NP-полна), проверки графов на изоморфизм (в тоже время существуют распределения, для которых неизвестно полиномиального алгоритма).

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

классов распределений, а не произвольные.

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

Вопрос 4. Верно ли, что любой «не очень сложный» язык можно упростить «не слишком сильно», усложнив распределение?

Вопрос 5. Верно ли, что существует «не слишком сложное» распределение, которое «сильно» усложняет язык?

Цели, полученные результаты и структура диссертации Цели работы.

5. Доказать нижние оценки на эвристическую схемную сложность эвристической версии класса MA.

6. Найти более простое доказательство эвристической иерархии для вероятностных вычиcлений с ограниченной ошибкой.

7. Найти более простое доказательство эвристической иерархии для недетерминированных вычислений.

8. Усилить известные условные теоремы об иерархии для вероятностных вычиcлений с ограниченной ошибкой.

5. Исследовать возможность улучшения параметра ошибки в теоремах об иерархии по времени для эвристических вычислений.

6. Доказать теорему об иерархии для эвристических вероятностных вычислений с ограниченной ошибкой на всех «простых» распределениях.

7. Построить такой язык, что он решается на «простом» распределении за полиномиальное время, но ни на каком «не очень сложном» распределении он не решается «быстрее».

8. Построить такое «не очень сложное» распределение и язык, что этот язык не решается за полиномиальное время на этом распределении, но решается на «простых» распределениях.

Научная новизна. Все результаты диссертации являются новыми. Теоретическая и практическая ценность. Работа носит теоретический характер. Ее результаты могут быть использованы в классической структурной теории сложности и теории сложности в среднем.

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

1. Доказана нижняя оценка на эвристическую схемную сложность эвристических полиномиальных протоколов Мерлин–Артур: доказано, что для любого выполняется HeurMA Heur_1-Size[].

2. Получено новое, более простое, доказательство того, что HeurBPP

Heur_12-BPTime[].

3) Получено новое, более простое, доказательство того, что NP

Heur_12-NTime[].

4) Доказано, что если существует односторонняя функция, то Р ^
Heur і __eBPTime[^fc].

5) Доказано, что для любых , _: и существует : {0,1}* —> [], такая,
что (,) Є Heur^FBPP, но (,) $_ Heur₁_i_₆FBPTime['ⁱ

6) Доказано, что для любых , и существует язык , такой, что
(,) Є Heur^BPP, но (,) qL Heiiri__eBPTime[^fc] для любого

Є DSamp[^fc].

7) Доказано, что для любых > 0 и > 0 существуют такой язык и
распределение Є Dbamp[ ^{g [п,}\, что \,) 0 Heur₁ і Р и

2 (log log log ⁿ)^c

для любого Є PSamp верно, что (,) Є Heur і DTimej].

2 (log log log n)^c

8) Доказано, что для любого > 0 существуют такой язык и распределе
ние Є PSamp, что (,) 4 Heurj_P и для любого Є DSamp[^al
верно, что (,) Є Heur₀/j_\DTime[].

Апробация работы. Результаты диссертационной работы были изложены на следующих конференциях и семинарах.

3. Международная конференция “Eighth International Conference on Computability, Complexity and Randomness” (Москва, CCR 2013).

4. Международная конференция “The 10th International Computer Science Symposium in Russia” (Иркутск, CSR 2015).

5. Семинар лаборатории “Exploring limits of computations” (Токио, 2015).

6. Международная конференция “The 26th International Symposium on Algorithms and Computation” (Нагоя, ISAAC 2015).

7. Международная конференция “Problems in Theoretical Computer Science” (Москва, 2015).

6. Международный семинар “Special Semester Program on Complexity Theory” (Санкт-Петербург, 2016).

7. Международная конференция “The 27th International Symposium on Algorithms and Computation” (Сидней, ISAAC 2016).

Публикации. Основные результаты диссертации опубликованы в рецензируемых научных изданиях [],[],[], входящих в список рекомендованных ВАК.

Работы [] и [] написаны в соавторстве. В работе [] идея применения теоремы об иерархии по времени моделирования распределения для доказательства теорем об иерархии для эвристических вычислений была придумана в неразделимом соавторстве с Д.М. Ицыксоном. При этом техническая реализации всех доказательств теорем об иерархии для эвристических вычислений в классах BPP, NP и FBPP принадлежит диссертанту. Условная теорема об иерархии по времени для вероятностных вычислений при условии существования односторонних функций была доказана в неразделимом соавторстве с Д.М. Ицыксоном и Д.О. Соколовым. В работе [] диссертанту принадлежит доказательство иерархии для слабого варианта трудности задачи в среднем и и доказательство теоремы об иерархии по времени моделирования распределения для бесконечно малых статистических расстояний, при этом постановка задачи принадлежит Д.М. Ицыксону. Неупомянутые результаты работ принадлежат соавторам.

Структура и объем работы. Диссертация состоит из введения, четырех глав и списка литературы. Общий объем диссертации 66 страниц. Список литературы включает 40 наименований на 5 страницах.

Классы распределений

Теперь определим классы распределенных задач, которые будем изучать. Сначала определим эвристические аналоги класса Р.

Определение 1.1 ([28]). 1) Класс Heurj(n)DTime[/(n)] состоит из распределенных задач (L, D), таких, что существует детерминированный алгоритм А(х): работающий 0(f(n)) шагов, и для любого п верно, что Рг [А(х) = L(x)] 1 — д(п). Также определим Heur,5(n)P = (J Heur(5(n)DTime[nfc]. k 0 2) Класс Avg(5(n)DTime[/(n)] состоит из распределенных задач (L, D), таких, что существует детерминированный алгоритм А(х): работающий 0(f(n)) шагов, для любого п верно, что Рг [А{х) =_1_] 8(п): и для любого х верно, что А(х) Є {L(x)i-L}. Также определим Avgj/n)P = (J Avgj/n)DTime[nfc]. к 0

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

Определение 1.2. 1) Класс Heurj(n)BPTime[/(n)] состоит из распределенных задач (L,D), таких, что существует вероятностный алгоритм А(х): работающий 0(f(n)) шагов, и для любого п верно, что Рг [Рг[Л(ж) = L{x)\ -т] 1 — 5(п). Также определим x Dn Heur,5(n)BPP = J Heurj(n)BPTime[nfc]. к 0 2) Класс Avg(5(n)BPTime[/(n)] состоит из распределенных задач (L, D), таких, что существует вероятностный алгоритм А(х): работающий 0(f(n)) шагов, для любого п верно, что Рг [Рг[Л(ж) =_L ] g] 3(п) и для любого х верно, что Рг[Л(ж) {L(x),-L}} -. Также определим Avg BPP = J Avgj/n)BPTime[nfc]. к0 Теперь определим равномерные по ошибке классы (определения даются по аналогии с определениями [29]). В этих классах искомая ошибка передается на вход алгоритму. Определение 1.3. 1) Класс HeurDTime[/(n)] состоит из распределенных задач (L, D), таких, что существует детерминированный алгоритм А(х, д), работающий 0(/(f)) шагов, и для любых п и 6 верно, что Рг [А(х,5) = L(x)] 1 — д. Также определим HeurP = x -Dn (J HeurDTime[nfc]. k 0 2) Класс AvgDTime[/(n)] состоит из распределенных задач (L, D), таких, что существует детерминированный алгоритм А, работающий 0(/(т)) шагов, для любых п и 6 верно, что Рг [А(х, 5) =_1_] 5 и для любого х верно, что А(х,д) Є {L(x)i-L}. Также определим AvgP = (J AvgDTime[nfc].

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

Определение 1.4. 1) Будем называть булевой схемой от переменных #1, ..., хп помеченный ориентированный ациклический граф с входящей степенью вершин 0 или 2, в вершинах входящей степени 0 которого стоят переменные х\, ..., хп, а каждая внутренняя вершина помечена бинарной булевой функцией. Значение булевой схемы на подстановке значений г і, ..., vn переменным х\, ..., хп — это строка значений, вычесленных в вершинах исходящей степени 0. Значение вычисленное в вершине, помеченной переменной ХІ — это Vi, а значение, вычисленное во внутренней вершине — это значение функции, которой помечена вершина, на значениях, вычисленных в двух ее предках. Размером схемы будем называть размер графа. Размером схемы С будем называть количество вершин в графе и обозначать его \С\. 2) Аналогично будем называть вероятностной булевой схемой от переменных я?і, ..., хп со случайными битами булеву схему от переменных Х\, . . . , ХП, Г\, ..., гт. 3) Язык L принадлежит классу Size[/(n)] тогда и только тогда, когда существует семейство булевых схем Сп, такое, что \Сп\ f(n) и для любого х Є {0,1} выполняется равенство С\х\{х) = L(x). 4) Язык L принадлежит классу BPSize[/(n)] тогда и только тогда, когда существует семейство вероятностных булевых схем Сп, такое, что \Сп\ f(n) и для любого х Є {0,1} выполняется Рг[Сж(ж) = L(x)} т (вероятность берется по случайным битам cхемы). 5) Распределенная задача (L, D) принадлежит классу Heurj(n)Size[/(n)] тогда и только тогда, когда существует семейство булевых схем Сп, такое, что \Сп\ f{n) и Рг [Сж(ж) = L(x)] 1 — д(п). 6) Распределенная задача (L, D) принадлежит классу Heur(5(n)BPSize[/(n)] тогда и только тогда, когда существу ет семейство булевых схем Сп, такое, что \Сп\ f{n) и Рг [Рг[Сж(ж) = L{x)\ ] 1 — 5(п) (вложенная вероят ность берется по случайным битам схемы). Определение 1.5. Распределенная задача {L,D) имеет эвристический протокол Мерлин-Артур (будем обозначать это как (L,D) Є HeurMA) тогда и только тогда, когда существует вероятностный алгоритм А(х, у, 5) (здесь х — вход, у — доказательство Мерлина и 6 — параметр уверенности), а также семейство множеств {Snj С {0, l}n},5Q+;nN (большие множества, где протокол работает корректно), такие, что для всех п и 6

Эвристические сведения

Таким образом, получаем следствие: Следствие 2.1. Если предположение 2.1 выполнено, то NP Size[nfc] для любого к Є Q+. Из работы [37] известно, что PromiseMA Size[nfc] алгебраизу-ется, а NP Size[nfc] не алгебраизуется. В то же время, неизвестно, алгебраизуется ли HeurMA Heurj_Size[nfc]. Таким образом, было бы па интересно найти препятствия на пути усиления результата про HeurMA до результата про HeurNP. В остатке этой главы мы докажем, что гипотеза 2.1 в некотором смысле не релятивизуется.

Все известные доказательства вложения МА С AM используют амплификацию (заключающуюся в повторении протокола) вероятности успеха. Получающийся протокол использует число случайных битов, пропорциональное размеру доказательства Мерлина. Мы докажем, что для моделирования МА-протокола АМ-протоколами необходимо итерировать эти протоколы.

Определение 2.6. Пусть /: {0,1} — {0,1}, к Є N. Будем говорить, что L Є АМ тогда и только тогда, когда существует оракульный вероятностный алгоритм А (х,у,г) (Артур), такой, что для любого ж, С и г, Артур делает не больше к запросов к оракулу, для любого х Є {0,1}п х Є L = Рг[ЗС А (х, С, г) = 1] = 1 f 1 ж 0 L = РгНб Л (ж, С, г) = II —, А(х,С,г) работает ро1у(ж) шагов. Определение 2.7. Пусть /: {0,1} — {0,1}, А; Є N. Будем говорить, что L Є МА тогда и только тогда, когда существует оракульный вероятностный алгоритм А(х,у,г) (Артур), такой, что для любого ж, С и г, Артур делает не больше к запросов к оракулу, для любого х Є {0,1}п х є L = ЗО Рг[Л (ж, С, г) = 1] = 1 f 1 ж 0 L = V6 Pr L4/ (ж, С, г) = II г 2 А(х,С,г) работает ро1у(ж) шагов. Теорема 2.6. Существует /, такая, что МА-1 AM 1 . Так как мы не можем итерировать протоколы из АМ , оставаясь в АМ-" , эта теорема непрямо указывает на то, что для моделирования итерировать необходимо. Пусть /: N х {0,1} х {0,1} — {0,1}. Будем обозначать Lf язык {0п3у Є {0,1} f(n,y, 0) = f(n,y,l)}. Лемма 2.8. Для любого отображения / язык Lf Є МА 1.

Доказательство. Рассмотрим следующий алгоритм для Артура: Артур получает у и z от Мерлина, берет случайную строку г Є {0,1} и про веряет, что z = f(n,y,r). Очевидно, что если 0П Є Lf, то вероятность ошибки 0, и если 0n Lf, то вероятность ошибки не больше 2. П Лемма 2.9. Существует отображение /, такое, что Lf АМ . Доказательство. Перечислим все полиномиальные оракульные алгоритмы А , которые могут использоваться как Артур. Предположим, что А имеет полиномиальный будильнику. Пусть п\ = 1 и п \ = Рг(щ) + 1. Заметим, что А на входах длины щ делает запросы ко входам с длиной меньше чем ПІ-\-\. Будем говорить, что А не имеет ложноотрицательных ответов на функции /, если 0Щ Є Lf = ЗС PrL4;f (0Пі, С, г) = 1] = 1, и не имеет ложноположительных ответов на функции /, если О г 0 Lf = V6 РгЬФ; (0 % 6, г) = II -.

Для любого пф щ, любых у и Ъ мы определим /(n, y,b) = b (тем самым Lf С {0Піі Є N}). Покажем, что существует /, такое, что для любого п алгоритм А п работает некорректно на / (не соблюдает ограничения на вероятность или дает некорректные ответы). Строить / будем последовательно для каждой длины. Точнее, мы построим последовательность функций f\: N х {0,1} х {0,1} — {0,1}, таких что /_i(n,y,&) = 6, а для каждого і 0 и п щ выполнено, что fi(n,y,b) = fi-i(n,y,b) и А имеет ложноположительные или ложноотрицательные ответы на f\. Также для каждого і 0 и п = щ определим f(n,y,b) = fi(n,y,b).

Докажем существование f\ от противного. Предположим, что для любой функции h: N х {0,1} х {0,1} — {0,1} алгоритм А не имеет ложноположительных или ложноотрицательных ответов на /г, если для любого і 0, п щ, у Є {0,1} и Ъ Є {0,1} выполняется h(n,y,b) = fi-i(n,y,b).

Для каждого у Є {0,1} рассмотрим ду, такое, что для любого z выполняется gy(rii y z) = 0, ду(щ, 1 — у, z) = ги gy(n,y,b) = fi-i(n,y,b) для всех п щ и b Є {0,1}.

В связи с тем, что А" не имеет ложноотрицательных ответов на ду, для всех г, у и і существует такое Су, что А?у (0Щ, Су, г) = 1. Заметим, что для всех j и у алгоритм А (0щ,Су,г) спрашивает оракул с вероятностью не меньше тГ В противном случае Артур имел бы ложноположи

Иерархия для HeurBPP

В этой секции при помощи того же метода доказывается теорема об иерархии для эвристической версии NP.

Определение 3.1. Ансамбль случайных величин 7п недетерминирова-но сэмплируем за время 0(f(n)) с использованием пк случайных битов тогда и только тогда, когда существует такой недетерминированный алгоритм А, что на входе (1п,г) он работает 0(f(n)) шагов и Л(1п,г) распределено так же, как и 7п, если г распределено равномерно на {0,1}п . Мы обозначим множество ансамблей, сэмплируемых за время 0(f(n)) с использованием пк случайных битов, как NSampnfc[/(n)].

Для доказательства иерархии эвристической версии NTime нам понадобятся булевы сэмплеры, введенные в работе [40] вместо миксеров, которые использовал Первышев. На самом деле не очень важно, использовать ли сэмплеры или миксеры, но сэмплеры позволяют сделать изложение более элегантным. Определение 3.2. Введем обозначение / = /С f{x), где жє{0,1}« /: {0,1}п —{0,1}. Булев сэмплер — это вероятностный оракульный алгоритм S, принимающий на вход целое число п и рациональные числа 6, є, имеющий оракульный доступ к функции /: {0,1}п — {0,1}, делает несколько неадаптивных запросов к функции / и возвращающий такое число q из отрезка [0,1], что Pr[\q — f\ є] 5. Булев сэмплер называется усредняющим, если он возвращает среднее значение запрошенных значений. Теорема 3.9 ([40]). Существует усредняющий булев сэмплер S, использующий п случайных бит, делающий q(n,e,S) = 0{ ц) запросов и работающий полиномиальное от п, - и -? время. Следствие 3.1. Существует усредняющий булев сэмплер S, использующий п — \ случайных битов, делающий q(n,e,S) = 0(щ) запросов и работающий полиномиальное от п, - и -? время.

Доказательство. Пусть S — это сэмплер из теоремы 3.9. Определим алгоритм S следующим образом: на входе (п,е,д) наш алгоритм возвращает \S (n — 1, є, І) + hS in — 1, є, I), где fn, f\ : {0, l}n_1 — {0,1} и /о(ж) = f(x0), fi(x) = f(xl), S?0 и S 1 используют одни и те же П — 1 случайных битов. Заметим, что t 1 = f . Значит, Pr LS (п, є, -) — / є 2 f ( - f - 6 5 Pr LS-/0(n, є, ) — jo є І + Pr ол(п, є, о) — j\\ є —І— = о. 2 2 2 П

Следующая теорема аналогична теореме 3.1 для распределений, сэмплируемых недетерминированными алгоритмами с фиксированным числом случайных битов. В доказательстве теоремы 3.1 мы считали вероятность того, что 7п = 1, простым сэмплированием, теперь мы для экономии случайных битов воспользуемся сэмплерами. Теорема 3.10. Для любого а 0 и є 0 существуют Ъ 0 и такой ансамбль случайных величин 7п NSampn[n6], принимающий значения из {0,1}, что для любого ансамбля ап Є NSampn[na] со значениями из {0,1} существует такое п, что статистическое расстояние между ап и 7п как минимум — є.

Доказательство. Мы будем использовать отложенную диагонализа-цию. Пусть ЕІ — перечисление всех недетерминированных алгоритмов (мы будем интерпретировать их как генераторы случайных величин использующие п случайных битов); мы предположим, что все ЕІ оснащены будильником, который останавливает исполнение на входе (1п,г) после na+1 шагов. Пусть S — это булев сэмплер из следствия 3.1. Определим последовательность щ следующим образом п\ = 1, щ+\ = п + 1 и п = 2Пі . Теперь рассмотрим случайную величину 7п, которая сэмплируется следующим алгоритмом Г(1п,г) (г (— Un — строка случайных битов) для таких п, что щ п п : если п = п , то Г(1п,г) всегда возвращает элемент {0,1} с самой маленькой вероятностью относительно ЕІ(1Щ,Г), где г равномерно распределено на {0,1}п, это может быть сделано простым перебором; если rij п п — 1, то запустим SH\n+l, I, 4), используя г в каче-стве случайных битов, где / : {0,1}п+1 — {0,1} и /(z) = Ei(ln+l, z); затем вернем 1, если результат больше и 0 в противном случае; Здесь мы используем, что S — усредняющий сэмплер, и недетерминированные вычисления замкнуты относительно монотонных операций.

Пусть ап сэмплируется недетерминированным алгоритмом Л(1п,г), использующим п случайных битов и работающим 0(па) шагов. В соответствии с построением последовательности ЕІ существует такое і, что ЕІ эквивалентен А. Докажем от противного, что существует такое п (n І п п ), что Ah/n,an) h — е. Предположим, что это не так.

Строгая сложность

Доказательство. Заметим, что если а(п) = о((3(п)), то а(п) = о(у/ а(п)/3(п)) и л а{п)(3{п) = о{(3{п)). 1 — 2. Применим утверждение 1 к а = 2а. Пусть АІ — это перечисление всех детерминированных алгоритмов с будильником nL5a. Будем рассматривать АІ как генераторы распределений и интерпретировать результат их работы как строки из {0,1}п каким-то фиксированным образом. Пусть F — это алгоритм, который сэмплирует ансамбль распределений следующим образом: на входе Xа с вероятностью \ он возвра щает результат работы Ai(ln), с вероятностью результат работы А2(1п)..., с вероятностью 2 т — результат работы An_i(ln) и с вероят ностью Ьт результат работы Ап{\п). Пусть F определяет ансамбль On—l On— 1 распределений Е. Очевидно, что Е Є DSamp[na]. Условие 1 влечет, что {L,E) Є Heura(n)P. Пусть Т разрешает (Ь,Е) в классе Неига(п)Р. Обозначим Sn = {х Є {0,1}п Т(ж) т L(x)}. Значит, En{Sn) а(п) для всех п. Таким образом, для любого R Є DSamp[na] существует такая константа С, что Rn(Sn) Са(п): что ,в свою очередь, меньше чем \/а{п)(3{п) (для достаточно больших п). Так как (L,D) Heur#(n)P, мы знаем, что D(Sn) (3(п). В итоге мы нашли такие последовательности натуральных чисел 1п и множеств Sn С {0,1}/п, что выполнены следующие условия: D(Sn) (3(ln) для всех п; Для всех R Є DSamp[na] и достаточно больших п выполняется неравенство R(Sn) л,/а(п)(3(п). 2 — 3. Доказательство аналогично концу доказательства леммы 4.1. Применим утверждение 2ка = а + 1. Пусть Aj — это перечисление всех алгоритмов с будильником 0(па); будем, как обычно, рассматривать их как генераторы ансамблей распределений. Пусть F — это алгоритм, который сэмплирует некоторый ансамбль распределений следующим образом: на входе 1п с вероятностью возвращает Ai(ln), с вероятностью т 2 возвращает Л2(1п), ..., с вероятностью т возвращает An_i(ln) и с вероятностью 2 т возвращает Лп(1п). Пусть Е — это ансамбль распределений, сэмплируемый F. Очевидно, что Е Є DSamp[na+1]. Пусть D и Sn — из утверждения 2 для а = а + 1. Определим такое множество / = {пі,П2, }, что оно состоит из всех таких п, что En{Sn) а(п).

Определим язык L С \J Sn. Пусть Т — это перечисление всех ал пЄІ горитмов. Определим так L, что для любого х Є Snk: х Є L тогда и только тогда, когда Т& не останавливается или отвергает на входе х. По определению (L, D) ф Heur#(n)R. Рассмотрим алгоритм, который возвращает 0 на всех входах. Если R Є DSamp[na], то существует такое і, что АІ сэмплирует R. Для п і для любого множества S С {0,1}п верно следующее неравенство: E(S) 2 lR(S). Значит, для любого ансамбля R из DSamp[na] этот алгоритм имеет ошибку не больше са(п) (где с — это константа, зависящая только от ансамбля R); са(п) л,/а(п)(3(п) для достаточно больших п.

Мы докажем утверждение, чуть более слабое, чем утверждение 2 из предложения 4.1. Фактически, мы докажем утверждение 2 при а(п) = 0(п) = Л. Данное рассуждение несложно обобщить на случай других бесконечно убывающих функций.

Для всех целых а 0 и Ъ 0 существуют такие ансамбль распределений D Є PSamp, последовательность целых чисел 1п и последовательность множеств Sn С {0,1}/п, что следующие условия выполнены: D(Sn) w для всех п; для любого F Є DSamp[na] выполнено F(Sn) для бесконечно многих п.

Начнем с неформального объяснения доказательства. Для простоты сначала докажем оценку вместо 4. Будем использовать отложенную диагонализацию. Рассмотрим целочисленные последовательности п и п , такие, что Пі = 1, щ = п + 1, п = 2Пі. Пусть Fi — это такое перечисление всех вероятностных алгоритмов с будильником na+1, что каждый алгоритм встречается бесконечно много раз в этом перечислении. Будем рассматривать Fi как генераторы распределений.

Обозначим за То;П и Т\іП множества бинарных строк длины п, начинающиеся с 0 и 1 соответственно. Рассмотрим следующий генератор распределения Dn: если п = п , найдем такое ti Є {0,1}, что Pr[F (lni) Є Tti ni] I и вернем случайный элемент из Tti n ; если Щ п п , то запустим F (ln+1), и если строка, которую он вернул, начинается с s Є {0,1}, вернем случайный элемент из Ts n.

Предположим, что существует такое распределение Е Є DSamp[na], что для всех п По, если для некоторого S С {0,1}п выполнено неравенство Pr[Dn Є S] 2, то Pr[F (ln) Є 5і] 2. Пусть F — это генератор для этого распределения Е и і по. Мы знаем, что Pr[Dn Є Т і;Гг ] = 1, а значит, Pr[Fi(ln» ) Є 7 .;П ] , значит, Pr[Dn _i Є Ttun -i] и так далее. В итоге мы получим, что Pr[F (lni) Є Tt./n.] , а это противоречит определению j.

Для доли ошибки т" доказательство будет аналогично, но мы разо-бьем {0,1}п на к частей. Однако возникнет новая проблема, заключающаяся в том, что при доле ошибки Л на разных длинах будет разное число отрезков; поэтому мы будем рассматривать деревья интервалов вместо цепей.

Доказательство теоремы 4.2. Рассмотрим такое перечисление всех вероятностных алгоритмов F{ с будильником na+1, что каждый алгоритм встречается бесконечно много раз в этом перечислении. Будем рассматривать Fi как генераторы для распределений. Рассмотрим целочисленные последовательности щ ип , такие, что п\ = 1, щ = 2п , п = 2Пі.

Разобьем множество строк длины п на пь непустых подмножеств; будем называть их интервалами и обозначать их Tj/n для j Є {1,2,..., nb}. Определим следующий граф (этот граф будет лесом):