Введение
Цели, полученные результаты и структура диссертации 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
Литература
