Содержание к диссертации
Введение
1 Введение 4
1.1 Иерархии по времени для эвристических алгоритмов . 7
1.1.1 Постановка задачи 7
1.1.2 Результаты 8
1.2 Иерархии по времени для алгоритмов с подсказкой . 10
1.2.1 Постановка задачи 10
1.2.2 Результаты 11
1.3 Иерархии по времени для криптографических примитивов 12
1.3.1 Постановка задачи 12
1.3.2 Результаты 13
1.4 Обзор литературы 14
2 Предварительные сведения 18
2.1 Модели вычислений синтаксические и семантические . 18
2.2 Примеры вычислительных моделей 20
2.2.1 Недетерминированные машины 21
2.2.2 Вероятностные машины 21
2.2.3 Однораундовые игры 23
2.3 Эвристические алгоритмы 25
2.4 Алгоритмы с подсказкой 26
2.5 Метод отложенной диагонализации 28
2.5.1 Нумерация вычислительных машин 29
2.5.2 Доказательство иерархии для NP 31
3 Иерархии по времени для эвристических алгоритмов 35
3.1 Конструкция одного семейства графов-миксеров 35
3.1.1 Графы-расширители 37
3.1.2 Лемма о перемешивании 38
3.1.3 Графы-миксеры 40
3.2 Иерархия для эвристик из NP 43
3.3 Иерархия для эвристик из ВРР 46
3.4 Иерархия для эвристик из МА 53
3.5 Некоторые обобщения 60
3.6 Открытые вопросы 62
4 Иерархии по времени для алгоритмов с подсказкой 64
4.1 Иерархия для алгоритмов из ZPP с подсказкой 64
4.2 Уплотнение иерархии 69
4.3 Некоторые обобщения 72
5 Иерархии по времени для криптографических примитивов 74
5.1 Односторонние функции 74
5.2 Одна лемма об односторонних функциях 76
5.3 Иерархия функций по времени обращения 78
5.4 Доказательство иерархии 80
5.5 Обобщения и открытые вопросы 87
Литература 88
- Иерархии по времени для алгоритмов с подсказкой
- Метод отложенной диагонализации
- Лемма о перемешивании
- Уплотнение иерархии
Введение к работе
Вопрос о том, дает ли большее количество вычислительных ресурсов возможность решать более трудные задачи, способствовал развитию теоретической информатики в начале 60-х годов. В одной из самых первых работ по вычислительной теории сложности Ю. Хартманис и Р. Стирнс [16] доказали наличие иерархии детерминированных алгоритмов по времени: существует язык, который может быть распознан некоторым детерминированным алгоритмом за время 0(п/г+б), но не может быть распознан никаким детерминированным алгоритмом за время 0(пк). Иными словами, чуть большее количество времени в самом деле позволяет решать более сложные задачи.
За детерминированными алгоритмами настал черед других вычислительных моделей. Так, в начале 70-х годов С. Кук [7] первым показал, что иерархия по времени существует также и для недетерминированных алгоритмов. Несколькими годами позже, Дж. Сейферас, М. Фишер и А. Мей-ер [22] предложили альтернативное доказательство иерархии по времени для недетерминированных алгоритмов. Однако, классической стала работа [28], в которой С. Жак для доказательства этой иерархии приме-
нил технику, получившую в дальнейшем название "отложенная диаго-нализация". Отметим, что эта техника позволяет доказать иерархию по времени не только для недетерминированных машин, но и для практически любой иной синтаксической модели вычислений.
Коротко поясним различие между синтаксическими и семантическими моделями вычислений. В любой синтаксической модели существует процедура, способная по описанию машины определить принадлежность этой машины к данной модели. В моделях же семантических подобная проверяющая процедура отсутствует, что вызвано наличием в семантических моделях требований, предъявляемых к поведению машин (например, вероятностная машина не должна превышать ограничение на вероятность ошибки). Выполнимость подобных семантических требований обычно невозможно проверить по описанию машины.
Вопрос о существовании иерархий по времени в семантических моделях остается открытым уже несколько десятков лет. Интерес к этому вопросу объясняется тем, что различные типы вероятностных алгоритмов задаются именно семантическими моделями. Среди наиболее распространенных семантических моделей можно выделить вероятностные алгоритмы с ограниченной двусторонней ошибкой, с ограниченной односторонней ошибкой и без ошибки (последним, однако, позволено с некоторой вероятностью не выдавать ответ). Эти классы алгоритмов широко распространены на практике, но ни для одного из них существование иерархии по времени недоказано.
В последние годы предметом рассмотрения стали алгоритмы с подсказкой, являющиеся промежуточным вариантом между машинами Тьюринга и вычислительными схемами. В серии работ [5, 8, 10], авторами
которых являются Б. Барак, Л. Фортноу, Р. Сантаиам и Л. Тревисан, был получен следующий результат. Иерархия по времени существует для вероятностных алгоритмов с ограниченной двусторонней ошибкой, пользующихся одним битом подсказки (один и тот же бит подсказки ап дается вместе с каждым входом длины п). В тех же работах было показано существование иерархии для вероятностных алгоритмов с односторонней ошибкой и одним битом подсказки. Статья [10] в качестве открытого вопроса указывает существование иерархии для алгоритмов с одним битом подсказки в других семантических моделях, в частности, в модели вероятностных алгоритмов без ошибки.
Помимо алгоритмов с подсказкой, последние исследования затрагивают существование иерархии для эвристических алгоритмов. Эвристические алгоритмы — это такие алгоритмы, которые решают задачу правильно на большинстве входов, но могут ошибаться на небольшой доле входов. Л. Фортноу и Р. Сантанам в работе [8] показали наличие иерархии по времени для вероятностных эвристических алгоритмов с ограниченной двусторонней ошибкой. Аналогичный результат верен и для квантового аналога указанного класса эвристических алгоритмов.
В обзорной статье [9] те же авторы в качестве открытого оставляют вопрос о существовании иерархий для эвристических алгоритмов в прочих семантических моделях (например, для эвристик в модели однора-ундовых игр), а также в некоторых синтаксических моделях (таких как недетерминированные эвристические алгоритмы).
Иерархии по времени для алгоритмов с подсказкой
Алгоритм с подсказкой задается машиной Тьюринга М и последовательностью строк {ап}=1, называемых подсказками. Машина М с каждым входом х получает соответствующую ему подсказку а\х\. То есть входам одной длины соответствует одна и та же подсказка, но, при этом, входам разных длин могут соответствовать разные подсказки. Формальное определение читатель может найти в разделе 2.4. Важным параметром алгоритма с подсказкой является длина подсказки 1{п) — \ап\. Даже с одним битом подсказки (т.е. при 1{п) = 1) машины Тьюринга способны распознавать некоторые языки, которые не распознаются машинами Тьюринга без подсказки.
Отметим, что чем длиннее подсказка, тем больше подобные алгоритмы напоминают вычислительные схемы, и, с другой стороны, чем короче подсказка, тем больше они напоминают обычные машины Тьюринга. Л. Фортноу и Р. Сантанам в работе [8] доказывают иерархию по времени для вероятностных алгоритмов с ограниченной двусторонней ошибкой и одним битом подсказки. Теорема. Для любых положительных cud, где с d, Здесь, BPTime[nd]/l обозначает класс языков, распознаваемых вероятностными алгоритмами с ограниченной двусторонней ошибкой за вре мя 0(nd) с одним битом подсказки. За формальным определением читатель может обратиться к разделу 2.4. Л. Фортноу, Р. Сантанам и Л. Тревисан в работе [ 10] с использованием той же техники доказывают иерархию для вероятностных алгоритмов с ограниченной односторонней ошибкой и одним битом подсказки. Теорема. Для любых положительных cud, где с d, В той же работе дается доказательство иерархии по времени для квазиполиномиальных по времени вероятностных алгоритмов без ошибки, пользующихся одним битом подсказки. Теорема. Для любого числа а 1 существует некоторое число Д, такое что Известно, что применение той же техники позволяет доказать аналогичную иерархию по времени для практически любой иной модели вычислений, основанной на машинах Тьюринга. Открытым является вопрос о существовании иерархии для полиномиальных по времени алгоритмов в такой модели, как, скажем, вероятностные алгоритмы без ошибки с одним битом подсказки. Мы доказываем, что существует иерархия для полиномиальных по времени вероятностных алгоритмов без ошибки, пользующихся одним битом подсказки. Следствие 4.1.
Для любых положительных end, где с d, Наша техника позволяет доказать аналогичную иерархию по времени для алгоритмов с одним битом подсказки из практически любой другой модели вычислений, основанной на машинах Тьюринга. Однако, мы воздержимся от формализации этого утверждения в данной работе.
Предложенная нами техника отличается от той, которая использовалась в предшествующих работах. Мы можем кратко охарактеризовать ее как "метод диагонализации с ветвлением". В теории вычислительной сложности традиционно рассматриваются задачи распознавания языков, т.е. задачи вычисления той или иной предикатной функции. Этого класса задач оказывается достаточно для исследования основных свойств вычислительных процессов. Тем не менее для криптографических исследований подобный уровень абстракции оказывается недостаточным. В криптографии в качестве основных абстракций традиционно используют некоторый набор криптографических примитивов, таких как односторонняя функция, функция с секретом, криптографически стойкая хэш-функция или же система шифрования с открытым ключом. Функции, легко вычислимые, но трудно обратимые, являются, пожалуй, самым базовым криптографическим примитивом и называются односторонними функциями. Задача обращения (взлома) конкретной легко вычислимой функции не описывается в терминах распознавания языков. Поэтому мы ставим вопрос о существовании иерархии по времени в криптографических терминах: верно ли, что, имея чуть больше времени, можно обратить большее количество различных легко вычислимых функций?
Метод отложенной диагонализации
Отложенная диагонализация является весьма удобной техникой доказательства иерархий по времени. Предложенная в работе [28], она позволяет доказать иерархию по времени в любой синтаксической модели вычислений. В этом разделе мы объясним метод отложенной диагонализации на примере доказательства классического результата — иерархии по времени для недетерминированных алгоритмов. Читатель, уже знакомый с этой техникой, может опустить приводимое ниже доказательство. Однако, заметим, что некоторые технические детали, общие для всех доказательств иерархий по времени, подробно обсуждаются лишь в этом разделе. Мы намеренно сформулировали иерархию по времени довольно слабым образом. Это позволит нам сконцентрироваться на существенных моментах доказательства иерархии. В действительности, известны более сильные утверждения. Например, Теорема 2.2 выводится из теоремы 2.1 с помощью техники "набивки" {padding technique). Отметим, что теорему 2.2 (и даже более сильные утверждения) можно также получить напрямую. Вернемся к теореме 2.1. Для ее доказательства достаточно предъявить некоторую недетерминированную машину N, обладающую следующими свойствами: 1. Машина N работает полиномиальное время, т.е. совершает полиномиальное от п число шагов на входах длины п. 2. Для любой машины М, работающей время 0(пс), существует некоторый вход х, на котором машины N и М дают противоположные ответы.
Понятно, что язык LN, распознаваемый подобной машиной N, принадлежит классу языков NP, но не принадлежит классу NTIME[nc]. Остается построить подобную машину N. При доказательстве иерархий по времени (в частности, иерархии по времени для недетерминированных алгоритмов) нам потребуется нумерация машин {Мг}, обладающая следующими свойствами: 1. Для любой синтаксически корректной машины М из данной модели, работающей время 0(пс), в нумерации встречается бесконечно много машин Мг, согласующихся с М (в смысле Ум(ж) = Умг(х)) на любом входе х, длина которого больше некоторого пм 2. Любая машина МІ на входе длины п может быть просимулирована за время poly(n:log2i), где полином универсален для всех машин 3. Ответ любой машины МІ на входе х длины п (т.е. VMXX)) может быть детерминировано вычислен за время poly(2nC ,log2i), где полином универсален для всех машин МІ. Для модели недетерминированных машин, подобную нумерацию {Мг} можно получить следующим образом.
Воспользуемся каким-нибудь естественным способом записи недетерминированных машин Тьюринга, в котором каждая машина может быть представлена бесконечно большим числом способов. Возьмем машину Мг, описание которой есть двоичное представление числа г. Машину МІ получим из машины Мг с помощью следующей модификации. Работа машины Мг состоит из двух этапов. На первом этапе, машина Мг вычисляет значение пс+1 и записывает его на отдельной лепте в единичной системе счисления. На втором этапе, машина Мг непосредственно выполняет программу машины Мг. При этом, с каждым шагом, машина М% стирает ровно один символ с ленты, содержавшей перед началом второго этапа число пс+1 в единичной системе счисления. Когда эта лента оказывается пустой, машина МІ останавливаемся. Таким образом, машина МІ совершает 0(пс+1) шагов на первом этапе и ровно пс+1 шагов на втором. Построенная нумерация {Мг} обладает заявленными свойствами. В самом деле, пусть М есть недетерминированная машина, работающая время 7м п- Начиная с некоторого пм выполняется неравенство 7м (пм)с {пм)с+1- Следовательно, существует бесконечно много машин Мі, согласующихся с М на любом входе длины большей, чем пм Касательно симуляции, заметим, что любая машина МІ останавливается после 0(пс+1) шагов, а длина записи МІ есть log2 г. Поэтому машину МІ можно просимулировать за время poly(n, log2 г).
Лемма о перемешивании
Доказательство. Обозначим _ п/2 J через т и рассмотрим граф-расширитель Маргулиса на 22т вершинах. Если п четно, то в качестве графа Gn мы можем взять этот самый граф, в котором каждое ребро удвоено.
Перейдем к случаю нечетного п. Пусть М есть матрица смежности выбранного графа. Эта матрица, будучи симметричной и положительно определенной, имеет ортогональную систему собственных векторов {Vi}, соответствующих собственным числам Aj. Пусть граф Gn имеет матрицу смежности М , где
Очевидно, число вершин полученного графа Gn есть 2П, каждая из которых имеет степень 16. Заметим, что
Кроме того, система векторов {(vi,Vi)T, {щ, —Vi)T}i является ортонормаль-ным базисом. Следовательно, второе по величине собственное число графа Gn есть 2 5\/2, и граф Gn является (2П, 16, Юл/2) -расширителем. П
Докажем модификацию хорошо известной леммы о перемешивающих свойствах графов-расширителей (см. [18, лемма 2.5]). Суть модификации заключается в довольно простом обобщении леммы на случай нечетких множеств вершин.
Определение 3.2 (Нечеткое множество). Пусть множество V состоит из N элементов. Нечеткое множество А СУ задается своим характеристическим вектором хл = {а ъ O N), Щ Є [0,1]. Мощность нечеткого множества А обозначается через \А\ и определяется как \А\ — Ylyev ХА{У) Пусть некоторый граф G = (У, Е) обладает матрицей смежности М. Рассмотрим два нечетких множества вершин А:В С. V. Количество ребер между двумя нечеткими множествами вершин е(А, В) определим как Доказательство. Будем следовать доказательству леммы 2.5 из [18].
Выберем ортонормированный базис {щ}, состоящий из собственных векторов матрицы М. Каждому вектору щ соответствует собственное число Лг-. Пусть Лі Лг ... Адг- Поскольку граф-расширитель G регулярен, имеем Ai = d. Кроме того, в качестве щ можем выбрать
Рассмотрим два произвольных нечетких множества Аи В с характеристическими векторами ХА И ХВ- Разложим характеристические вектора по базису {щ}:
Данная сумма может быть ограничена сверху с использованием неравенства Коши-Буняковского-Шварца: Остается заметить, что, поскольку ХА, ХВ Є [0,1] , верны следующие неравенства: Для удобства обозначим множество вида {1,..., N} через [N].
Определение 3.3. Пусть G = ([М], [Л ], ) является двудольным графом, вершины левой доли которого имеют степень d. Пусть для каждого подмножества вершин правой доли В, такого что \В\ (1/2 — є)N2, существует не более 5Ni вершин v в левой доле, таких что Г(г ) П В\ d/2. Тогда граф G называется (е, )-миксером.
Уплотнение иерархии
Доказательство. Данное утверждение выводится из Теоремы 4.1 с помощью техники, известной под названием "padding". Сразу оговоримся, что, не умаляя общности, числа с и d можно считать рациональными. Более того, поскольку случай с 1 доказывается довольно просто (за время 0{nd) машина успевает прочитать больше битов на входе, чем за время 0(пс)\ будем считать, что с 1. Предположим, что сформулированное нами следствие не верно, т.е. Тогда выполняется следующее утверждение, которое противоречит Теореме 4.1: Утверждение 4.2. Исходя из нашего предположения, для любого натурального к имеем Докажем данное утверждение индукцией по к. Случай к = 0 следует из предположения (4.8), поэтому будем считать, что к 0. Рассмотрим произвольный язык Этот язык распознается некоторой вероятностной машиной М с однобитовой подсказкой а. При этом, машина М с подсказкой а работает время 0(ncr ) и является семантически корректной в смысле отсутствия ошибки. Определим В этот язык могут входить лишь те слова, которые имеют длину из множества { r(n)}neN. Покажем, что Для этого построим распознающую этот язык машину N с подсказкой /3 следующим образом. Подсказку (За для входов длины а(п) положим равной ап, а для остальных входов подсказку /3 можно определить произвольным образом. Машина N с подсказкой (5 на входе у длины т работает следующим образом: Отметим, что {х,(Зт) — (х,а \х\). Тогда, поскольку М с подсказкой а семантически корректна, то и Л " с подсказкой (5 семантически безупречна. Касательно времени работы машины N, заметим, что оно есть Действительно, при фиксированном к, извлечение строки х из строки у длины т можно осуществить за время 0{т) 4- polyilogm), где первое слагаемое тратится на чтение строки у, а второе — на арифметические операции. Далее, поскольку машина М известна заранее, ее можно встроить в машину N.
Поэтому симуляция машины М не требует дополнитель-ных временных затрат, и на нее уходит лишь время 0(тсг ). Итак, мы показали, что выполняется пункт (4.10), а следовательно, по индукционному предположению имеем Это означает, что язык V распознается некоторой вероятностной машиной N с однобитовой подсказкой а , такими что N с подсказкой работает время 0{псгк 1) и является семантически корректной. Используя быструю машину N , попробуем построить новую машину М с подсказкой а , которая распознавала бы язык L быстрее, чем машина М с подсказкой а. Положим а п = Р агпу На входе х длины п, машина М с подсказкой Ы работает следующим образом: Отметим, что (у,а п) = {y,(3[v\), и, поскольку N с подсказкой (3 се-мантически корректна, то и М с подсказкой Ы является семантически корректной. Касательно времени работы машины М , укажем, что оно есть Теорема 4.1 и Следствие 4.1 могут обобщены на случай подсказки, состоящей из нескольких битов: Теорема 4.2. Для любого положительного с и любого натурального а,
Следствие 4.2. Для любых положительных cud, где с d, и любого натурального а, Доказательство Теоремы 4.1 можно распространить на случай подсказки длины а, произведя лишь одну существенную модификацию. Необходимо перейти от двоичного дерева, участвовавшего в доказательстве, к дереву, в котором вершины имеют 2а детей. Доказательство Следствия 4.1 переносится на случай подсказки длины а без существенных изменений. Отметим, и это важно, что полученные Теорема 4.2 и Следствие 4.2 выполняются для практически любой модели вычислений. Читатель может самостоятельно убедиться в том, что приведенные доказательства не используют каких бы то ни было специфических свойств вероятностных алгоритмов без ошибки.
