Теоретические оценки времени работы алгоритмов для задачи выполнимости булевых формул

• Автор: Гирш, Эдуард Алексеевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 1998
• Место защиты: Санкт-Петербург
• Количество страниц: 154 с.

Оглавление
Введение
Метод расщеплений
Метод поиска локального максимума
Структура диссертации
1 Основные понятия
1.1 Формулы и наборы
1.2 Классы формул в КНФ
1.3 Вычислительные задачи
1.4 Модели вычислений
2 Общая схема алгоритма расщепления для ВЫП
2.1 Дерево расщепления
2.2 Оценка количества вершин в дереве расщепления
2.3 Описание общей схемы
2.4 Правила преобразования, сохраняющие выполнимость
3 Алгоритм расщепления для произвольных формул в КНФ
3.1 Правило черных и белых литералов
3.2 Верхняя оценка относительно количества дизъюнкций
3.3 Верхняя оценка относительно длины формулы
4 Алгоритм расщепления для формул в КНФ-(1,ос)
4.1 Дополнительные правила преобразования
4.2 Процедура Reduce для формул в КНФ-(1,оо)
4.3 Верхняя оценка относительно количества дизъюнкций
4.4 Верхняя оценка относительно длины формулы
4.5 Верхняя оценка относительно количества переменных

5 Алгоритм расщепления для формул в fc-КНФ, имеющих
много выполняющих наборов
5.1 Описание алгоритма
5.2 Формулировки основных результатов
5.3 Анализ алгоритма
5.4 Формулы в КНФ без “коротких” выполняющих наборов
6 Алгоритмы расщепления для задачи максимальной выполнимости
6.1 Общая схема алгоритма для МАКС-ВЫП, основанного на методе расщеплений
6.2 Правила преобразования, сохраняющие максимальное количество выполненных дизъюнкций
6.3 Верхние оценки для МАКС-ВЫП и МАКС-2-ВЫП
6.4 Верхняя оценка для МАКС-З-ВЫП
7 Алгоритмы поиска локального максимума
7.1 Верхняя оценка
7.2 Нижняя оценка
Литература
Введение
Язык булевых формул является удобным языком для кодирования многих важных алгоритмических задач, например, встречающихся в теории расписаний, верификации программ, потоковых задач. Любая задача, решаемая на недетерминированной машине Тьюринга за полиномиальное время, сводится к задаче выполнимости булевых формул (см., например, [1, 30]). Задача о выполнимости булевой формулы остается МР-полной, даже если рассматривать формулы в конъюнктивной нормальной форме (КНФ), состоящие из дизъюнкций, длины которых не превосходят трех; можно также считать, что каждая переменная входит в формулу не более трех раз. Все известные алгоритмы для задачи о выполнимости формулы в КНФ и ее подзадач с указанными ограничениями имеют экспоненциальные верхние оценки времени исполнения “в наихудшем случае”, причем все эти оценки имеют вид с”, где с — некоторая константа, ап — либо длина формулы, либо количество дизъюнкций, либо количество входящих в формулу переменных.
Чаще всего задача выполнимости формулы в КНФ (ВЫП) определяется как задача распознавания: требуется выяснить, существует ли набор истинностных значений переменных, при котором формула становится истинной (выполняющий набор). В качестве результата выдается один из двух ответов: “Выполнима” или “Невыполнима”.
Поскольку все рассматриваемые в данной диссертации алгоритмы для задачи ВЫП находят выполняющий набор, будем рассматривать ВЫП как задачу поиска: алгоритм, решающий ее, выдает для выполнимой формулы выполняющий набор, а для невыполнимой — ответ “Невыполнима” . С задачей выполнимости также тесно связана задача максимальной выполнимости формулы в КНФ (МАКС-ВЫП), в которой

2.1 Дерево расщепления
Большая часть алгоритмов, представленных в данной диссертации, использует метод расщепления. Исполнению такого алгоритма соответствует некоторое дерево, называемое деревом расщепления. В этом разделе описываются понятие дерева расщепления и некоторые связанные с ним характеристики, необходимые для оценки количества вершин в нем (и, тем самым, времени работы алгоритма).
Под деревом расщепления будем понимать дерево, вершины которого помечены формулами в КНФ таким образом, что если некоторая вершина помечена формулой К, то ее сыновья помечены некоторыми более простыми формулами Д, Д
Б формул Иг будем называть расщеплением). Пример дерева расщепления приведен на рис. 2.1. В более широком смысле, вершины дерева расщепления могут быть помечены объектами более сложной природы, например, в главе 5 вершины будут помечены парами, состоящими из формулы и некоторого множества. В этом и следующем разделах для нас будет несущественно, какими именно объектами помечены вершины дерева расщепления.
Сопоставим каждому объекту И некоторое неотрицательное число д(И) [сложность И, или мера сложности Г). Будем рассматривать исключительно деревья расщепления, в которых каждая вершина обладает свойством, что сложность объекта, которым она помечена, больше сложности каждого из объектов, которыми помечены ее сыновья. В этой диссертации, за исключением главы 5, объектами будут формулы в КНФ, а в качестве д будет выбираться количество переменных, входящих в