Введение
1 Функции переменных со сложностью не менее 23
1.1 Основные определения 23
1.2 Пример последовательности функций трёхзначной логики с экспоненциальной глубиной 30
1.3 Формулировка основного результата главы 37
1.4 Доказательство вспомогательных утверждений 39
1.5 Доказательство основной теоремы главы 44
2 Понижение значности логики с качественным сохранением нижней оценки 52
2.1 Формулировка основного результата главы 52
2.2 Доказательство вспомогательных утверждений 54
2.3 Доказательство основной теоремы главы 61
2.4 Уточнение нижней оценки 72
3 Высокие оценки сложности в бесконечных базисах 74
3.1 Сравнение роста сложности в конечных и бесконечных базисах для различных моделей 74
3.2 Простой пример высокой нижней оценки в бесконечном базисе
3.3 Построение класса с одинаковой сверхэкспоненциальной асимптотикой сложности в конечном и бесконечном базисах 80
3.4 Высокие оценки глубины функций трёхзначной логики из классов, не имеющих конечного базиса 88
3.5 Высокие оценки сложности функций четырёхзначной логики из классов, не имеющих конечного базиса 93
Заключение 98
Список литературы
