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

Оглавление
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 Обобщения и открытые вопросы
Литература