Введение
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
