Вычислительная сложность некоторых задач математической логики

Оглавление
Введение
1 Основные понятия и определения
1.1 Классы сложности и типы сводимости
1.2 Логические программы
2 Сложность параллельности для хорновского фрагмента линейной логики
2.1 Основные понятия линейной логики
2.2 Перестановочность, параллельность и сильная параллельность
2.3 Максимальная параллельность.
3 Сложность обновлений моделей логических программ
3.1 Постановка задачи.
3.2 Определения.
3.3 Сложность задач при фиксированной сигнатуре.
3.3.1 Вспомогательная конструкция Л и Т
3.3.2 Алгоритм построения обновления для хорновских ЛП
3.3.3 Ф хорновская, А положительно.
3.3.4 Ф хорновская, Д произвольно
3.3.5 Общий случай.
3.4 Случай нефиксированной сигнатуры
4 Сложность совершенных моделей пропозициональных логических программ
4.1 Совершенные модели логических программ.
4.2 Определения
4.3 Структура совершенных моделей
4.4 Нижняя оценка сложности совершенных моделей
5 О структуре полных множеств для и X
5.1 Основные понятия и определения .
5.1.1 Структурная теория сложности.
5.1.2 Информационная сложность проблем
5.2 Алгоритмическая сложность и плотность
трудных множеств
5.3 О множествах, сводимых к множествам с большой колмого
ровской сложностью
Заключение
Литература