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

• Автор: Дудаков, Сергей Михайлович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Тверь
• Количество страниц: 139 с.

Оглавление
Введение
1 Основные понятия и определения
1.1 Классы сложности и типы сводимости
1.2 Логические программы
2 Сложность параллельности для хорновского фрагмента линейной логики
2.1 Основные понятия линейной логики
2.2 Перестановочность, параллельность и сильная параллельность
2.3 Максимальная параллельность
3 Сложность обновлений моделей логических программ
3.1 Постановка задачи
3.2 Определения
3.3 Сложность задач при фиксированной сигнатуре
3.3.1 Вспомогательная конструкция: 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 О структуре полных множеств для NP и EXP
5.1 Основные понятия и определения
5.1.1 Структурная теория сложности
5.1.2 Информационная сложность проблем
5.2 Алгоритмическая сложность и плотность
NP-трудных множеств
5.3 О множествах, сводимых к множествам с большой колмого-
ровской сложностью
Заключение
Литература

Список иллюстраций
2.1 Алгоритм FINDMAX
4.1 Алгоритм PERFCONS
4.2 Алгоритм PERFC0NS1
5.1 Алгоритм RESTORE

символов у в и) равняется
к + (ах — За) +
А так как у > к + 1, то применима предпоследняя импликация.
4 случай. Предположим, применены все импликации, соответствующие числам задачи, и получена конъюнкция ии1. Тогда т' содержит не менее
п + (а — а)-
символов г. Следовательно, применима последняя импликация,
Итак, чтобы последовательность была перестановочной необходимо и достаточно, чтобы она была перестановочна на единственной нерассмот-
и Оп
реннои конъюнкции
5 случай. Рассмотрим следующую последовательность применения: выберем произвольную тройку чисел из задачи З-РАЗБИЕНИЕ с суммой равной а, применим импликации, соответствующие числам этой тройки (это будет максимальная подпоследовательность), получим уаг2а. После этого применим (уаг2а -> у%а). Заметим, что в данном случае каждый раз применяется максимальная подпоследовательность, имеющая максимально возможную длину (это будет использовано в следующем параграфе).
Если разбиение чисел а* существует, то проделав этот цикл т раз мы по-
/ Од
лучим конъюнкцию т — у , и все импликации, соответствующие числам задачи, будут использованы. Следовательно, ни одна из двух оставшихся импликаций не будет применима. Если разбиения нет, то рано или поздно соответствующую тройку найти станет невозможно. Следовательно, в результате получится конъюнкция «/, в которой или количество у будет меньше а, или количество 2 — меньше 2а. Единственная возможность — применить (г —у МАХ).
Осталось только отметить, что приведенная последовательность импли-

кации всегда применима к у
уба+аа-а, р у6а+аМАХ.