Введение к работе
Актуальность темы. Язык булевых формул является удобным языком для кодирования многих важных алгоритмических задач, например, встречающихся в теории расписаний, верификации программ, потоковых задач. Любая задача, решаемая на недетерминированной машине Тьюринга за полиномиальное время, сводится к задаче выполнимости булевых формул (см., например, [1]). Задача о выполнимости булевой формулы остается NP-полноЙ, даже если рассматривать формулы в конъюнктивной нормальной форме (КНФ), состоящие из дизъюнкций, длины которых не превосходят трех; можно также считать, что каждая переменная входит в формулу не более трех раз.
Один из самых популярных алгоритмов для задачи выполнимости был предложен М. Денисом и Х.Патнемом [5] и сформулирован в более современном виде М. Девисом, Г. Лоджеманиом и Д. Лавлендом [4]. Его основой является метод расщеплений. Количество промежуточных формул, порождаемых этим алгоритмом, может достигать 2N для формулы с N переменными. На настоящий момент для многих частных случаев существуют более эффективные алгоритмы, однако, большинство из них в той или иной степени использует метод расщеплений. Оценка 2N была впервые улучшена в начале 1980х годов Б.Мониеном и Э.Шпекенмейером [11, 13] и Е.Я.Данцпным [2] для формул в к-КНФ, т.е. формул, состоящих из дизъюнкций, длины которых не превосходят к. Они описали алгоритм, который, используя метод расщеплений, решает задачу выполнимости для этих формул за время ф(к — l)'vp(L) (здесь и далее ф(к) — единственный положительный корень уравнения
хк - хк~1 - ... - х - 1 = О,
L — длина формулы, К — количество дизъюнкций в ней, N — количество переменных, р — некоторый полином). В частности, для случая 3-КНФ эта оценка составляет (f>N, где ф и 1.6181 — "золотое сечение". Недавно результат для fc-КНФ был улучшен до 2*1_1^>*vp(L) Р. Патури,
П. Пудлаком и Ф. Зейном [14] с помощью вероятностного алгоритма. Они же привели детерминированный алгоритм, время работы которого приближается к 2^l^2k^№p(L) с ростом к. Для частного случая 3-КНФ результаты улучшались многократно, текущий рекорд составляет приблизительно 1.5jVp(L) (работы О. Кулльманна [8] и И.Шиермейера [16]). Исследования по улучшению экспоненциальных верхних оценок велись и для других классов формул — например, Х.Люкхардт [10] описал класс КНФ~(1,оо), для формул которого выполнимость можно проверить за время l.M23Np(L).
Снижение верхних оценок для задачи выполнимости актуально не только по отношению к количеству переменных, встречающихся в формуле, но и по отношению к другим ее параметрам. Для произвольных формул в КНФ первые нетривиальные верхние оценки были получены относительно длины формулы и количества входящих в нее дизъюнкций. Наилучшие оценки на данный момент составляют 1.0801^р(Ь) [9] и 1.2600*р() [12].
Для каждого из этих случаев неизвестны нетривиальные нижние оденки. С другой стороны, всякое снижение основания экспоненты в верхних оценках приводит к значительному расширению класса фор-мул, выполнимость которых можно реально проверить с помощью компьютера. Поэтому интерес представляют новые алгоритмы для задачи выполнимости, имеющие лучшие верхние оценки, в частности, оценки с меньшим основанием экспоненты.
В то время как доказанные верхние оценки остаются весьма далекими от нижних, некоторые исследователи проводили работу по экспериментальному изучению свойств алгоритмов для задачи выполнимости. В ходе этих исследований было выявлено, что многие эвристические алгоритмы работают достаточно эффективно. Особенно это относится к алгоритмам, основанным на методе поиска локального максимума: эксперименты показали их практическую пригодность к решению задач о п ферзях, раскраске графа [18], задач, возникающих при синтезе схем и
плаїшровании [17]. Поэтому важным вопросом является доказательство верхних и нижних оценок на время исполнения ив наихудшем случае" для алгоритмов, использующих поиск локального максимума. До настоящего времени такие результаты не были известны.
Другой важной задачей, близкой к задаче выполнимости, является задача максимальной выполнимости: требуется найти набор истинностных значений, выполняющий наибольшее число дизъюнкций входной формулы. Эта задача является MAXSNP-полной. даже если входом алгоритма являются формулы в 2-КНФ [15]. За последние десять лет было предложено множество полиномиальных приближенных алгоритмов для этой задачи, например, за полиномиальное время можно найти набор для формулы в 3-КНФ, выполняющий долю 7/8 относительно максимального количества одновременно выполнимых дизъюнкций. С другой стороны, с помощью техники вероятностно проверяемых доказательств [3], было доказано, что в предположении Р ф NP существует "граница возможного приближения". Именно, имеется константа с, такая что не существует полиномиального алгоритма, который находил бы набор, выполняющий долю с + е относительно максимального количества одновременно выполнимых дизъюнкций. В частности, для формул в 3-КНФ эта константа составляет 7/8, а для формул в 2-КНФ — 0.955 (результаты Й. Хостада [7]). При этом остается открытым вопрос о том, за какое время можно найти набор, выполняющий долю, превосходящую указанную "границу возможного приблиокенгія" на произвольное е.
Цели работы. 1. Найти новые верхние оценки для задачи выполнимости и ее NP-полных подзадач, улучшив алгоритмы, основанные на методе расщепления.
2. Найти верхние и нижние оценки времени исполнения "в наихудшем случае" алгоритмов, основанных на методе поиска локального максимума.
3. Построить алгоритмы для точного и приближенного (с произвольной степенью точности) решения задачи максимальной выполнимости и найти верхние оценки времени их исполнения.
Общая методика работы. В работе используются методы, традиционные для теоретической информатики. В диссертации описан ряд конкретных алгоритмов, основанных на методе расщеплений и методе поиска локального максимума, доказаны верхние и нижние оценки на время их работы "в наихудшем случае". В качестве основной модели вычислений используется многоленточная машина Тьюринга.
Основные результаты работы. 1. Предложена новая техника, позволяющая улучшить алгоритмы для задачи выполнимости формул в КНФ, использующие метод расщепления. Полученные алгоритмы имеют лучшие, чем все ранее известные, верхние оценки для задачи ВЫП относительно длины формулы и количества дизъюнкций, а также оценки для ее NP-полных подзадач ВЫП-(1,оо) и А;-ВЫП-(1,оо), лучшие, чем для общего случая.
Рассмотрены формулы в fc-КНФ, имеющие много выполняющих наборов. Существует естественный вероятностный алгоритм, быстро находящий выполняющий набор для такой формулы. В работе строится его детерминированный аналог, решающий эту задачу за линейное время. Этот алгоритм также основан на методе расщепления. Выдаваемый им набор является "коротким", т.е. количество литералов, которые он включает, ограничено некоторой константой.
-
Впервые получены нетривиальные верхняя и нижняя оценки времени исполнения "в наихудшем случае" для алгоритма, решающего задачу выполнимости булевых формул на основе метода поиска локального максимума.
-
Предложена схема, позволяющая применить метод расщеплений к задаче максимальной выполнимости для нахождения как точных, так и приближенных решений. Впервые получены нетривиальные верх-
ние оценки для нахождения точных и приближенных (с произвольной степенью точности) решений задачи максимальной выполнимости для формул в КНФ, 2-КНФ и 3-КНФ. В частности, показано, что находящаяся "за пределами возможного приближения" задача нахождения приближения с точностью 7/8 + є для формулы в 3-КНФ, состоящей из К дизъюнкций, может быть решена за время, не превосходящее 2ієК (с точностью до полиномиального сомножителя).
Научная новизна. Все основные результаты диссертации являются новыми.
Практическая и теоретическая ценность. Работа носит теоретический характер, однако имеет и практические приложения. Разработанные алгоритмы могут быть реализованы и применяться на практике для решения различных комбинаторных задач, сводящихся к вопросу о выполнимости булевых формул, в частности, многих важных NP-полных задач. Найденные верхние и нижние оценки позволяют определить область практической применимости рассматриваемых алгоритмов.
Апробация работы. Результаты диссертации докладывались на заседании кафедры информатики С.-Петербургского государственного университета, на семинарах по математической логике и информатике ПОМИ РАН и Уппсальского Университета (Швеция), а также на международных конференциях по искусственному интеллекту (КІ-95, Биле-фельд, Германия, 1995), дискретным алгоритмам (SODA'98, Сан-Франциско, США, 1998) и теории алгоритмов (SWAT'98, Стокгольм, Швеция, 1998).
Публикации. Основные результаты диссертации изложены в восьми работах [19, 20, 21, 22, 23, 24, 25, 26], перечисленных в конце автореферата.
Сігруктура и объем диссертации. Диссертация состоит из введения и семи глав. Нумерация разделов, формул, алгоритмов, процедур, таблиц, рисунков, примеров, лемм и теорем ведется отдельно для каждой главы. Текст диссертации изложен на 149 страницах (исключая список литературы). Список литературы содержит 42 наименования.
