Введение
1 Необходимые определения 16
1.1 Синтаксис и семантика 16
1.2 Классы сложности 22
2 Основной результат 25
2.1 Формулировка основного результата 25
2.2 Модальные логики 26
2.2.1 Сложность проблемы разрешения в полном языке: вспомогательная конструкция 26
2.2.2 Сложность константного фрагмента логики К4 . 31
2.2.3 Интервал [К, К4] 36
2.2.4 Сложность фрагмента от одной переменной логики S4 37
2.2.5 Интервалы [К4, GL] и [К4, Grz] 41
2.2.6 Некоторые замечания и следствия 43
2.3 Базисная и формальная логики Виссера 44
2.3.1 Сложность проблемы разрешения позитивного фрагмента: вспомогательная конструкция
2.3.2 Сложность проблемы разрешения константного фрагмента логики BPL 48
2.3.3 Сложность проблемы разрешения фрагмента от одной переменной логики FPL 53
2.3.4 Некоторые замечания и следствия 58
2.4 Суперинтуиционистские логики 59
2.4.1 Сложность проблемы разрешения позитивного фрагмента: вспомогательная конструкция
2.4.2 Полшюмиальное погружеіше позитивного фрагмента Int в позитивный фрагмент Int с двумя переменными 61
2.4.3 Интервал [Int, КС] 70
2.4.4 Некоторые следствия 70
2.4.5 Некоторые сложностные аспекты фрагмента от двух переменных; логики КС 73
2.4.6 Обобщения и замечания 79
3 Анализ полученных результатов 82
3.1 Функция сложности 82
3.1.1 К истокам задачи 83
3.1.2 Оценка функции сложности в случае конечного числа переменных в языке 85
3.2 Комментарий 86
Библиография 91
