Иерархии по времени для некоторых классов эвристик, алгоритмов с подсказкой, криптографических примитивов

• Автор: Первышев, Константин Вячеславович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Санкт-Петербург
• Количество страниц: 91 с.

Оглавление
1 Введение

1.1 Иерархии по времени для эвристических алгоритмов . . .

1.1.1 Постановка задачи

1.1.2 Результаты

1.2 Иерархии по времени для алгоритмов с подсказкой . . . .

1.2.1 Постановка задачи

1.2.2 Результаты

1.3 Иерархии по времени для криптографических примитивов

1.3.1 Постановка задачи

1.3.2 Результаты

1.4 Обзор литературы.
2 Предварительные сведения
2.1 Модели вычислений синтаксические и семантические . . .
2.2 Примеры вычислительных моделей
2.2.1 Недетерминированные машины
2.2.2 Вероятностные машины
2.2.3 Однораундовые игры
2.3 Эвристические алгоритмы .
2.4 Алгоритмы с подсказкой
2.5 Метод отложенной диагонализации
2.5.1 Нумерация вычислительных машин.
2.5.2 Доказательство иерархии для Р.
3 Иерархии по времени для эвристических алгоритмов
3.1 Конструкция одного семейства графовмиксеров
3.1.1 Графырасширители
3.1.2 Лемма о перемешивании
3.1.3 Графымиксеры
3.2 Иерархия для эвристик из МР
3.3 Иерархия для эвристик из ВРР
3.4 Иерархия для эвристик из МА.
3.5 Некоторые обобщения
3.6 Открытые вопросы .
4 Иерархии по времени для алгоритмов с подсказкой
4.1 Иерархия для алгоритмов из 2РР с подсказкой.
4.2 Уплотнение иерархии.
4.3 Некоторые обобщения
5 Иерархии по времени для криптографических примитивов
5.1 Односторонние функции
5.2 Одна лемма об односторонних функциях
5.3 Иерархия функций по времени обращения
5.4 Доказательство иерархии.
5.5 Обобщения и открытые вопросы
Литература


Так, в начале -х годов С. Кук [7] первым показал, что иерархия по времени существует также и для недетерминированных алгоритмов. Несколькими годами позже, Дж. Сейферас, М. Фишер и А. Мейер [] предложили альтернативное доказательство иерархии по времени для недетерминированных алгоритмов. Однако, классической стала работа (], в которой С. Отметим, что эта техника позволяет доказать иерархию но времени не только для недетерминированных машин, но и дли практически любой иной синтаксической модели вычислений. Коротко поясним различие между синтаксическими и семантическими моделями вычислений. В любой синтаксической модели существует процедура, способная по описанию машины определить принадлежность этой машины к данной модели. В моделях же семантических подобная проверяющая процедура отсутствует, что вызвано наличием в семантических моделях требований, предъявляемых к поведению машин (например, вероятностная машина не должна превышать ограничение па вероятность ошибки). Выполнимость подобных семантических требований обыно невозможно проверить по описанию машины. Вопрос о существовании иерархий по времени в семантических моделях. Интерес к этому вопросу объясняется тем, что различные типы вероятностных алгоритмов задаются именно семантическими моделями. Среди наиболее распространенных семантических моделей можно выделить вероятностные алгоритмы с ограниченной двусторонней ошибкой, с ограниченной односторонней ошибкой и без ошибки (последним, однако, позволено с некоторой вероятностью не выдавать ответ). Эти классы алгоритмов широко распространены на практике, но ни для одного из них существование иерархии по времени не доказано. В последние годы предметом рассмотрения стали алгоритмы с подсказкой, являющиеся промежуточным вариантом между машинами Тьюринга и вычислительными схемами. В. Барак, Л. Фортноу, Р. Сантанам и Л. Тревисам, был получен следующий результат. Иерархия по времени существует для вероятностных алгоритмов с ограниченной двусторонней ошибкой, пользующихся одним битом подсказки, (один и тот же бит подсказки ап дается вместе с каждым входом длины п). В тех же работах было показано существование иерархии для вероятностных алгоритмов с односторонней ошибкой и одним битом подсказки. Статья [ ] в качестве открытого вопроса указывает существование иерархии для алгоритмов с одним битом подсказки в других семантических моделях, в частности, в модели вероятностных алгоритмов без ошибки. Помимо алгоритмов с подсказкой, последние исследования затрагивают существование иерархии для эвристических алгоритмов. Эвристические алгоритмы — это такие алгоритмы, которые решают задачу правильно на большинстве входов, но могут ошибаться на небольшой доле входов. Л. Фортноу и Р. Сантанам в работе [8] показали наличие иерархии по времени для вероятностных эвристических алгоритмов с ограниченной двусторонней ошибкой. Аналогичный результат верен и для квантового аналога указанного класса эвристических алгоритмов. В обзорной статье [9] те же авторы в качестве открытого оставляют вопрос о существовании иерархий для эвристических алгоритмов в прочих семантических моделях (например, для эвристик в модели однора-ундовых игр), а также в некоторых синтаксических моделях (таких как недетерминированные эвристические алгоритмы). Эвристический алгоритм для некоторой задачи есть такой алгоритм, который решает эту задачу на многих входах, но не обязательно на всех. Формально, будем говорить, что некоторый детерминированный алгоритм является (1 - ? Ь, если задающая его машина Тьюринга правильно вычисляет предикат Ь(х) на как минимум (1 —<)'(гс))-части входов# любой возможной длины п. На остальных входах алгоритму позволено выдавать неправильный ответ или, скажем, не останавливаться. Помимо детерминированных эвристических алгоритмов можно также определить различные виды вероятностных эвристических алгоритмов, недетерминированные эвристические алгоритмы и др. Формальные определения даны в разделе 2. Л. Фортноу и Р. Теорема. Ьеиг1»1/паВРР % Ьеиг1_1/п«ВРТ1те[п<].