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

\\Ofl ^

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи Гирш Эдуард Алексеевич

ТЕОРЕТИЧЕСКИЕ ОЦЕНКИ ВРЕМЕНИ РАБОТЫ АЛГОРИТМОВ ДЛЯ ЗАДАЧИ ВЫПОЛНИМОСТИ БУЛЕВЫХ ФОРМУЛ

(05.13.17 — теоретические основы информатики)

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

Санкт-Петербург — 1998

Работа выполнена в Санкт-Петербургском отделении Математического института им. В. А. Стеклова Российской Академии Наук

Научный руководитель — кандидат физико-математических

наук Е. Я. Даицин Официальные оппоненты — доктор физико-математических

наук Д. Ю. Григорьев — кандидат физико-математических наук И. П. Соловьев Ведущая организация — Санкт-Петербургский институт

информатики и автоматизации Российской Академии Наук

Защита диссертации состоится " " 1998 года

в Щ час. на заседании Диссертационного сонета К 063.57.54 по защите диссертаций на соискание учёной степени кандидата наук в Санкт-Петербургском государственном университете (198904, Санкт-Петербург, Старый Петергоф, Библиотечная пл., 2, математико-механичес-кий факультет Санкт-Петербургского государственного университета).

С диссертацией можно ознакомиться в научной библиотеке им. М.Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб. 7/9.

Автореферат разослан " " yx>JUbj±ä 199$ года.

Ученый секретарь

диссертационного совета

кандидат физико-математических наук

Б. К. Мартыненко

Общая характеристика работы.

Актуальность темы. Язык булевых формул является удобным языком для кодирования многих важных алгоритмических задач, например, встречающихся в теории расписаний, верификации программ, потоковых задач. Любая задача, решаемая на недетерминированной машине Тьюринга за полиномиальное время, сводится к задаче выполнимости булевых формул (см., например, [1]). Задача о выполнимости булевой формулы остается КР-полноЙ, даже если рассматривать формулы в конъюнктивной нормальной форме (КНФ), состоящие из дизъюнкций, длины которых не превосходят трех; можно также считать, что каждая переменная входит в формулу не более трех раз.

Один из самых популярных алгоритмов для задачи выполнимости был предложен М. Денисом и Х.Патнемом [5] и сформулирован в более современном виде М. Девисом, Г. Лоджеманиом и Д. Лавлендом [4]. Его основой является метод расщеплений. Количество промежуточных формул, порождаемых этим алгоритмом, может достигать 2" для формулы с N переменными. На настоящий момент для многих частных случаев существуют более эффективные алгоритмы, однако, большинство из них в той или иной степени использует метод расщеплений. Оценка 2" была впервые улучшена в начале 1930х годов Б.Мониеном и Э. Шпекенмейером [11, 13] и Е.Я.Данциным [2] для формул в /."-КНФ, т.е. формул, состоящих из дизъюнкций, длины которых не превосходят к. Они описали алгоритм, который, используя метод расщеплений, решает задачу выполнимости для этих формул за время ф(к — 1 )'чр(Ь) (здесь и далее ф(к) — единственный положительный корень уравнения

хк - х^ - ... - а- - 1 = О,

Ь — длина формулы, К — количество дизъюнкций в ней, N — количество переменных, р — некоторый полином). В частности, для случая 3-КНФ эта оценка составляет , где ф « 1.6181 — "золотое сечение". Недавно результат для &-КНФ был улучшен до р(Ь) Р. Патури,

П. Пудлаком и Ф. Зейном [14] с помощью вероятностного алгоритма. Они же привели детерминированный алгоритм, время работы которого приближается к 2р(Ь) с ростом к. Для частного случая 3-КНФ результаты улучшались многократно, текущий рекорд составляет приблизительно 1.5**р(Ь) (работы О. Кулльманна [8] и И.Шиермейера [16]). Исследования по улучшению экспоненциальных верхних оценок велись и для других классов формул — например, Х.Люкхардт [10] описал класс КНФ-(1,оо), для формул которого выполнимость можно проверить за время 1.4423лр(£).

Снижение верхних оценок для задачи выполнимости актуально не только по отношению к количеству переменных, встречающихся в формуле, но и по отношению к другим ее параметрам. Для произвольных формул в КНФ первые нетривиальные верхние оценки были получены относительно длины формулы и количества входящих в нее дизъюнкций. Наилучшие оценки на данный момент составляют 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. Предложена новая техника, позволяющая улучшить алгоритмы для задачи выполнимости формул в КНФ, использующие метод расщепления. Полученные алгоритмы имеют лучшие, чем все ранее известные, верхние оценки для задачи ВЫП относительно длины формулы и количества дизъюнкций, а также оценки для ее КР-полных подзадач ВЫП-(1,оо) и А;-ВЫП-(1,оо), лучшие, чем для общего случая.

Рассмотрены формулы в ¿-КНФ, имеющие много выполняющих наборов. Существует естественный вероятностный алгоритм, быстро находящий выполняющий набор для такой формулы. В работе строится его детерминированный аналог, решающий эту задачу за линейное время. Этот алгоритм также основан на методе расщепления. Выдаваемый им набор является "коротким", т.е. количество литералов, которые он включает, ограничено некоторой константой.

2. Впервые получены нетривиальные верхняя и нижняя оценки времени исполнения "в наихудшем случае" для алгоритма, решающего задачу выполнимости булевых формул на основе метода поиска локального максимума.

3. Предложена схема, позволяющая применить метод расщеплений к задаче максимальной выполнимости для нахождения как точных, так и приближенных решений. Впервые получены нетривиальные верх-

ние оценки для нахождения точных и приближенных (с произвольной степенью точности) решений задачи максимальной выполнимости для формул в КНФ, 2-КНФ и 3-КНФ. В частности, показано, что находящаяся "за пределами возможного приближения" задача нахождения приближения с точностью 7/8 + е для формулы в 3-КНФ, состоящей из К дизъюнкций, может быть решена за время, не превосходящее 2*еК (с точностью до полиномиального сомножителя).

Научная новизна. Все основные результаты диссертации являются новыми.

Практическая и теоретическая ценность. Работа носит теоретический характер, однако имеет и практические приложения. Разработанные алгоритмы могут быть реализованы и применяться на практике для решения различных комбинаторных задач, сводящихся к вопросу о выполнимости булевых формул, в частности, многих важных NP-полных задач. Найденные верхние и нижние оценки позволяют определить область практической применимости рассматриваемых алгоритмов.

Апробация работы. Результаты диссертации докладывались на заседании кафедры информатики С.-Петербургского государственного университета, на семинарах по математической логике и информатике ПОМИ РАН и Уппсальского Университета (Швеция), а также на международных конференциях по искусственному интеллекту (KI-95, Биле-фельд, Германия, 1995), дискретным алгоритмам (SODA'98, Сан-Франциско, США, 1998) и теории алгоритмов (SWAT'98, Стокгольм, Швеция, 1998).

Публикации. Основные результаты диссертации изложены в восьми работах [19, 20, 21, 22, 23, 24, 25, 26], перечисленных в конце автореферата.

Структура и объем диссертации. Диссертация состоит из введения и семи глав. Нумерация разделов, формул, алгоритмов, процедур, таблиц, рисунков, примеров, лемм и теорем ведется отдельно для каждой главы. Текст диссертации изложен на 149 страницах (исключая список литературы). Список литературы содержит 42 наименования.

Содержание работы

Определения и обозначения. Прежде всего приведем некоторые определения, необходимые для изложения содержания работы.

Пусть Var — множество булевых переменных. Отрицание переменной v обозначается V, множество отрицаний всех переменных из Var обозначается Var. Литералами называются элементы множества Lit = Var U Var, причем элементы Var называются положителънъши, а элементы Var — отрицательными литералами. Дизъюнкция определяется как конечное подмножество множества Lit, не содержащее никакой переменной вместе с ее отрицанием. Под формулой в конъюнктивной нормальной форме (КНФ), или просто формулой, будем понимать конечное множество дизъюнкций. Под длиной дизъюнкции будем понимать ее мощность как множества, под длиной формулы — сумму длин всех входящих в нее дизъюнкций. До конца автореферата L будет обозначать длину формулы, К — количество дизъюнкций в ней, N — количество переменных, р — некоторый полином.

Набором истинностных значений переменных (или, коротко, набором) называется конечное подмножество множества Lit, не содержащее никакой переменной вместе с отрицанием. Набор А присваивает истинное значение всякой переменной х, для которой х 6 А, и присваивает ложное значение всякой переменной у, для которой у € А (остальным переменным набор А не присваивает никаких значений).

Набор А выполняет дизъюнкцию D, если их пересечение как множеств непусто. Набор А называется выполняющим для формулы F,

если он выполняет каждую ее дизъгонкцшо. Выполнимой называется формула, для которой существует хотя бы один выполняющий набор; в противном случае формула называется невыполнимой.

Для целого числа к > 1, формула в к-КНФ не содержит дизъюнкций длины более к. Формула в КНФ-(1,со) определяется как формула, в которую никакой положительный литерал не входит более одного раза. Формулы в к-КНФ-(1,оо) принадлежат пересечению этих классов.

Алгоритм решает задачу ВЫП, если для выполнимой формулы он находит выполняющий набор, а для невыполнимой выдает ответ "Невыполнима". Вероятностный алгоритм в первом случае также может выдать ответ "Невыполнима", но вероятность этой ошибки не должна превышать 1 /2. Сужение задачи ВЫП на формулы в к-КНФ, КНФ-(1,оо) и т.д. будем обозначать соответственно к-ВЫП, ВЫП-(\,оо) и т.д.

До конца автореферата ф будет обозначать "золотое сечение" ^р®-, а ф(к) — единственный положительный корень полинома хк—хк~1 —. ..— 1.

Описание глав. Во введении обсуждается состояние исследований, связанных с темой диссертации, формулируются основные результаты диссертации, поясняется их положение и контексте текущих исследований, описывается структура диссертации.

В первой главе определяются основные понятия и вводятся обозначения, используемые на протяжении всей диссертации. В частности, определяются такие понятия, как формула в КНФ, набор истинностных значений, выполнимость формул; вводятся обозначения для мер сложности формулы, количества вхождений литерала в формулу и другие. Также определяются классы формул в КНФ с некоторыми дополнительными ограничениями (&-КНФ и др.). Приводятся соглашения об используемых моделях вычислений, определяется понятие приближенного алгоритма для МАКС-ВЫП.

Вторая глава посвящена общей схеме алгоритма для ВЫП, ис-

пользующего расщепление. Здесь определяется понятие дерева расщепления, описываются основные части алгоритма, основанного на методе расщеплений, доказывается теорема о его корректности и времени работы. Основной деталью, отличающейся у различных алгоритмов в рамках общей схемы, являются правила преобразования формул, сохраняющие выполнимость. В этой же главе перечисляются основные известные правила преобразования.

Во третьей главе приводятся алгоритмы для ВЫП, дающие новые верхние оценки для этой задачи. Эти алгоритмы основаны на методе расщепления. Формулируется новое правило преобразования формул — правило черных и белых литералов. Алгоритмы, построенные на основе этого правила, решают задачу выполнимости за время, не превосходящее 1.2389*р(£) и 1.0758£р(£).

В четвертой главе аналогичная техника применяется к формулам в КНФ-(1,ос). Все приводимые я ней алгоритмы используют метод расщеплений, а также правило черных и белых литералов. Здесь вводятся дополнительные правила преобразования, специфичные для КНФ-(1,оо). С помощью этих правил строятся алгоритмы, имеющие хорошие верхние оценки относительно различных параметров формулы. Именно, для формул в КНФ-(1,оо) доказываются оценки 1.1939Ар(Х) и 1.0644хр(£), для формул в 3-КНФ-(1,оо) доказывается оценка 1.3581яр(Ь), для формул в 4-КНФ-(1,оо) — оценка 1.41б1л'р(Ь), для формул в &-КНФ — оценка [21~еы^к + где ек 6 [0;0.5] — решение уравнения

еЦк- 1 =е&и^2е* + (1 -е*)1о§2 (1-е*).

Кроме того, оказывается, что для задачи выполнимости формул в &-КНФ-(1,оо) имеется вероятностный алгоритм, работающий время

Существует простой вероятностный алгоритм, быстро находящий выполняющий набор для формулы в &-КНФ, доля выполняющих наборов для которой ограничена снизу константой. В пятой главе приво-

дится детерминированный алгоритм, решающий эту задачу за линейное время. Этот алгоритм использует метод расщеплений, однако обходит дерево расщепления не в глубину, а в ширину. Выполняющий набор, выдаваемый этим алгоритмом, является "коротким", т.е. его мощность ограничена константой. В конце главы показывается, что, в отличие от формул в ¿-КНФ, формула в КНФ без ограничения на длину дизъюнкций может не иметь "коротких" выполняющих наборов, даже если половина всех наборов для нее — выполняющие.

В шестой главе метод расщеплений переносится на задачу максимальной выполнимости. Общая схема алгоритма, использующего метод расщеплений, дополняется для решения МАКС--ВЫП. Доказывается, что с помощью этой схемы можно находить как точные, так и приближенные (с произвольной степенью точности) решения. Приводятся правила преобразования формул, которые можно использовать при решении задачи максимальной выполнимости; показывается, как по точному или приближенному решению для преобразованной формулы найти решение для исходной. Общая схема применяется последовательно к формулам в КНФ, 2-КНФ и 3-КНФ, для каждого из этих классов доказывается верхняя оценка. Например, доказываются оценка фкр(Ь) для нахождения точного решения задачи максимальной выполнимости и оценка 2SeKp(L) (для вероятностного алгоритма) для нахождения набора для формулы в 3-КНФ, выполняющего долю 7/8 + е от максимального числа одновременно выполненных дизъюнкций (как отмечалось выше, детерминированный полиномиальный алгоритм для этой задачи может существовать только если Р = NP).

В седьмой главе изучаются алгоритмы, использующие метод поиска локального максимума. Доказывается верхняя оценка для известного алгоритма Я.П.Гента и Т.Уэлша [6] CSAT ("Cautious SAT"). Поведение этого алгоритма изучается в случае, если на вход ему подана формула в fc-КНФ-с/ (формула в ¿-КНФ, в которую каждая переменная входит не более d раз; задача выполнимости для таких формул NP-

полна при k,d > 3). Доказывается, что время работы алгоритма на таких формулах не превосходит 2yNq(N), где 7 = 1 - Для случая произвольных формул в КНФ доказывается нижняя оценка порядка 2N. Эта оценка справедлива как для алгоритма CSAT, так и для похожего на него алгоритма GSAT ("Greedy SAT"), предложенного Б.Селманом, Г.Левеком и Д.Митчеллом [18]. (Именно после публикации алгоритма GSAT в 1992 году резко возрос интерес к алгоритмам для ВЫП, использующим метод поиска локального максимума.)

Литература

[1] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Пер. с англ.— М.: Мир, 1982.— 416 с.

[2] Данцин Е. Я. Системы доказательства тавтолотечности, основанные на методе расщеплений.— Диссертация на соискание степени канд. ф.-м.н.— Л., ЛОМИ, 1983.— 98 с.

[3] Arora S. Probabilistic Checking of Proofs and Hardness of Approximation Problems // PhD Thesis.— UC Berkeley, 1994.— 150 p.

[4] Davis M-, Logemann G., Loveland D. A machine program for theoremproving // Comm. ACM.— 1962,— №5,— P. 394-397.

[5] Davis M., Putnam H. A computing procedure for quantification theory 11 J. Assoc. Сотр. Much — I960— №7 — P. 201-215.

[6] Gent I.P., Walsh T. Towards an understanding of hill-climbing procedures for SAT // Proceedings of the 11th National Conference on Artificial Intelligence.— AAA1 Press, 1993 — P. 28-33.

[7] Hastad J. Some optimal inapproximability results // Proceedings of the 29th Annual ACM Symposium on Theory of Computing.— 1997.— P. 110.

[8] Kullmann O. Worst-case Analysis, 3-SAT Decision and Lower Bounds: Approaches for Improved SAT Algorithms // DIM ACS Proceedings SAT Workshop 1996.— American Mathematical Society, 1996.— P. 261-313.

[9] Kullmann O., Luckhardt H. Deciding propositional tautologies: Algorithms and their complexity // Submitted to Information and Computation.— 1997.

[10] Luckhardt H. Obere Komplexitätsschranken für TAUT-Entscheidungen // Proceedings of Frege Conference.— Schwerine, Akademie-Verlag Berline, 1984 — P. 331-337.

[11] Monien B., Speckenmeyer E. 3-satisfiability is testable in 0(1.62r) steps.— Bericht Nr. 3/1979, Reihe Theoretische Informatik, UniversitätGesamthochschule-Paderborn.

[12] Monien B., Speckenmeyer E. Upper bounds for covering problems.— Bericht Nr. 7/1980, Reihe Theoretische Informatik, Universität-Gesamthochschule-Paderborn.

[13] Monien B., Speckenmeyer E. Solving satisfiability in less than 2" steps // Discrete Applied Mathematics.— 1985.— Vol.10.— P. 287-295.

[14] Paturi R., Pudlak P., Zane F. Satisfiability Coding Lemma // Proceedings of the 38th Annual Symposium, on Foundations of Computer Science.— 1997,— P. 566-574.

[15] Papadimitriou Ch.H. Computational Complexity.— Addison-Wesley, 1994,— 532 pp.

[16] Schiermeyer I. Pure literal look ahead: An 0(1.497") 3-Satisfiability algorithm // In: Workshop on the Satisfiability Problem, Technical Repört — Siena, 1996.— University Köln, Report No. 96-230.

[17] Selman B., Kautz H. Pushing the Envelope: Planning, Propositional Logic and Stochastic Search // Proceedings of the 13th National

Conference on Artificial Intelligence and the 8th Innovative Applications of Artificial Intelligence Conference.— AAAI Press/MIT Press, 1996.— Vol.2.—P. 1194-1201.

[18] Selman В., Levesque H., Mitchell D. A New Method for Solving Hard Satisfiability Problems // Proceedings of the 10th National Conference on Artificial Intelligence.— MIT Press, 1992.— P. 440-446.

Публикации автора по теме диссертации

[19] Hirsch Е.А. A Fast Deterministic Algorithm for Formulas That Have Many Satisfying Assignments // In: KI-95 Activities: Workshops, Posters, Demos.— Bonn, Gesselschaft fiir Informatik e.V., 1995.— P. 8788.

[20] Гирш Э.А. Принцип разделения знаков для задачи пропозициональной выполнимости // Записки научных семинаров ПОМИ.— СПб, 1997.— Т. 241.— С. 30-71.

[21] Hirsch Е.А. Deciding satisfiability of formulas with К clauses in less than 2аШ97К steps — PDMI preprint 4/1997,— 12 p.— Электронный адрес: http://www.pdmi.ras.ru/preprint/1997/97-04.html)

[22] Hirsch E.A. A Fast Deterministic Algorithm for Formulas That Have Many Satisfying Assignments // Logic Journal of the IGPL.— Oxford University Press, 1998.— Vol. 6, №1.— P. 59-71.

[23] Hirsch E.A. Two New Upper Bounds for SAT // Proceedings of the 9th Annual AGM-SIAM Symposium on Discrete Algorithms.— 1998.— P. 521-530.

[24] Dantsin E., Gavrilovich M., Hirsch E.A., Konev B. Approximation algorithms for MAX SAT: a better performance ratio at the cost of a longer running time.— PDMI preprint 14/1998.— 13 p.— Электронный адрес: http: Uwww. pdmi. ras. ru/preprint/1998/98-14. html

РОССИЙСКАЯ АКАДЕМИЯ НАУК САНКТ-ПЕТЕРБУРГСКОЕ ОТДЕЛЕНИЕ МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМ. В. А. СТЕКЛОВА

ТЕОРЕТИЧЕСКИЕ ОЦЕНКИ ВРЕМЕНИ РАБОТЫ АЛГОРИТМОВ ДЛЯ ЗАДАЧИ ВЫПОЛНИМОСТИ БУЛЕВЫХ ФОРМУЛ

(05.13.17 — теоретические основы информатики)

Диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель кандидат физико-математических наук старший научный сотрудник ПОМИ РАН Е. Я. Данцин

На правах рукописи

Гирш Эдуард Алексеевич

Санкт-Петербург — 1998

Оглавление

Введение 4

Метод расщеплений..................................................7

Метод поиска локального максимума..............................18

Структура диссертации..............................................21

1 Основные понятия 25

1.1 Формулы и наборы ............................................25

1.2 Классы формул в КНФ........................................28

1.3 Вычислительные задачи......................................29

1.4 Модели вычислений............................................30

2 Общая схема алгоритма расщепления для ВЫП 34

2.1 Дерево расщепления............................................35

2.2 Оценка количества вершин в дереве расщепления .... 38

2.3 Описание общей схемы........................................41

2.4 Правила преобразования, сохраняющие выполнимость . . 52

3 Алгоритм расщепления для произвольных формул в КНФ 55

3.1 Правило черных и белых литералов ........................55

3.2 Верхняя оценка относительно количества дизъюнкций . . 57

3.3 Верхняя оценка относительно длины формулы............64

4 Алгоритм расщепления для формул в КНФ-(1,оо) 77

4.1 Дополнительные правила преобразования..................79

4.2 Процедура Reduce для формул в КНФ-(1,сю)............81

4.3 Верхняя оценка относительно количества дизъюнкций . . 83

4.4 Верхняя оценка относительно длины формулы............91

4.5 Верхняя оценка относительно количества переменных . . 97

5 Алгоритм расщепления для формул в к-КНФ, имеющих много выполняющих наборов 108

5.1 Описание алгоритма......................109

5.2 Формулировки основных результатов........................110

5.3 Анализ алгоритма.......................112

5.4 Формулы в КНФ без "коротких" выполняющих наборов . 116

6 Алгоритмы расщепления для задачи максимальной выполнимости 118

6.1 Общая схема алгоритма для МАКС-ВЫП, основанного на методе расщеплений..................... . 118

6.2 Правила преобразования, сохраняющие максимальное количество выполненных дизъюнкций ........................129

6.3 Верхние оценки для МАКС-ВЫП и МАКС-2-ВЫП ... 130

6.4 Верхняя оценка для МАКС-З-ВЫП ........................133

7 Алгоритмы поиска локального максимума 136

7.1 Верхняя оценка................................................137

7.2 Нижняя оценка................................................145

Литература

150

Введение

Язык булевых формул является удобным языком для кодирования многих важных алгоритмических задач, например, встречающихся в теории расписаний, верификации программ, потоковых задач. Любая задача, решаемая на недетерминированной машине Тьюринга за полиномиальное время, сводится к задаче выполнимости булевых формул (см., например, [1, 30]). Задача о выполнимости булевой формулы остается КР-полной, даже если рассматривать формулы в конъюнктивной нормальной форме (КНФ), состоящие из дизъюнкций, длины которых не превосходят трех; можно также считать, что каждая переменная входит в формулу не более трех раз. Все известные алгоритмы для задачи о выполнимости формулы в КНФ и ее подзадач с указанными ограничениями имеют экспоненциальные верхние оценки времени исполнения "в наихудшем случае", причем все эта оценки имеют вид с", где с — некоторая константа, а п — либо длина формулы, либо количество дизъюнкций, либо количество входящих в формулу переменных.

Чаще всего задача выполнимости формулы в КНФ (ВЫЛ) определяется как задача распознавания: требуется выяснить, существует ли набор истинностных значений переменных, при котором формула становится истинной (выполняющий набор). В качестве результата выдается один из двух ответов: "Выполнима" или "Невыполнима". Поскольку все рассматриваемые в данной диссертации алгоритмы для задачи ВЫП находят выполняющий набор, будем рассматривать ВЫП как задачу поиска: алгоритм, решающий ее, выдает для выполнимой формулы выполняющий набор, а для невыполнимой — ответ "Невыполнима" . С задачей выполнимости также тесно связана задача максимальной выполнимости формулы в КНФ (МАКС-ВЫП), в которой

требуется найти набор, выполняющий как можно больше дизъюнкций входной формулы.

Исследования по алгоритмам для задачи выполнимости булевых формул велись по следующим основных направлениям:

— поиск классов формул, для которых задача выполнимости разрешима за полиномиальное время (см., например, обзор в [4]);

— понижение основания экспоненты в верхних оценках для ВЫП и ее NP-полных подзадач [27, 28, 2, 3, 29, 40, 32, 23, 24];

— оценка сложности доказательств невыполнимости в различных системах доказательств [39];

— создание приближенных алгоритмов для МАКС-ВЫП [41, 18, 14, 26, 38, 7, 21],

— компьютерные эксперименты, проясняющие эффективность алгоритмов для ВЫП и МАКС-ВЫП на определенных классах формул, там, где не доказаны хорошие верхние оценки [11, 37, 16].

Экспериментальные исследования наиболее широко проводились для алгоритмов, основанных на методе поиска локального максимума и методе расщеплений. Большая часть "экспоненциальных" алгоритмов для ВЫП и ее подзадач также основана на методе расщеплений. Два этих основных метода будут рассмотрены ниже подробнее.

В приближенных алгоритмах, предлагавшихся для МАКС-ВЫП, используются совершенно иные методы, чем в (точных) алгоритмах для ВЫП. Эти алгоритмы преобразуют МАКС-ВЫП в задачу полуопределенного программирования и находят за полиномиальное время приближенное решение. В общем случае полученный набор значений переменных выполняет долю 0.770 от максимального числа выполненных дизъюнкций [7]. Для формул в &-КНФ при к = 2,3 существуют более точные алгоритмы (формула находится в &-КНФ, если каждая ее дизъюнкция содержит не более к литералов). Алгоритм для фор-

мул в 3-КНФ [21] выполняет долю 7/8, алгоритм для формул в 2-КНФ [14] выполняет долю 0.931. Все указанные алгоритмы являются вероятностными, некоторые из них могут быть дерандомизированы (т.е. в них можно избавиться от случайного выбора). С другой стороны, исследования, касающиеся вероятностно проверяемых доказательств (см., например, [6]), привели к тому, что была показана невозможность при условии Р ф NP построения полиномиального по времени алгоритма, находящего приближение с долей, большей некоторой константы. Для формул, состоящих из дизъюнкций, содержащих не более, чем по два литерала, эта константа составляет 0.955 [20]. Если же разрешены дизъюнкции хотя бы из трех литералов, константа равна 7/8. Таким образом, в предположении Р ф NP, невозможно построение полиномиального алгоритма, который давал бы ответ со степенью приближения лишь на произвольное е большей, чем алгоритм X. Карлоффа и У. Цвика. Алгоритмы, дающие ответ с такой степенью приближения и имеющие экспоненциальную сложность, меньшую, чем сложность алгоритма, находящего точное решение, неизвестны.

Из алгоритмов для ВЫП, не использующих ни метод расщепления, ни метод поиска локального максимума, стоит отметить новый результат Р. Патури, П.Пудлака и Ф. Зейна [31]: доказано, что выполнимость формулы в &-КНФ можно выяснить вероятностным алгоритмом за время, не превосходящее p(L)2(l~l/k)N, а детерминированным алгоритмом — за время, приближающееся к p(L)с ростом к (здесь и далее р — некоторый полином, L — длина входной формулы, К — количество дизъюнкций в ней, N — количество переменных). Эти алгоритмы дают наилучшие известные на данный момент оценки относительно количества переменных: вероятностный — для к > 4, а детерминированный — для к > 5.

Решение алгоритмических задач тесно связано с системами до-

казательств. Из существования системы доказательств, в которой имелись бы полиномиальные доказательства невыполнимости булевых формул, следовало бы NP = coNP [39]. Экспоненциальная нижняя оценка на длину таких доказательств была впервые доказана Г. С. Цейтиным [5] для регулярных резолюций. Впоследствии эта оценка неоднократно улучшалась и была обобщена на случай обычных резолюций. Этот результат представляется особенно важным, поскольку метод расщепления тесно связан с резолюционными доказательствами [10]. Позднее были доказаны экспоненциальные нижние оценки для некоторых других систем, например, резолюций и систем Фреге ограниченной глубины. Обзор таких результатов имеется в [39].

Метод расщеплений

Наиболее широко в литературе по задаче выполнимости булевых формул представлены алгоритмы, основанные на методе расщеплений, восходящем к [13] и [12]. Этот метод состоит в том, что задача выполнимости для исходной формулы сводится к задаче выполнимости для нескольких более простых формул; в простейшем случае задача выполнимости для формулы F сводится к задаче выполнимости для формул F[x] и F[x] для некоторой переменной х (для литерала /, формула F[l] получается из формулы F удалением всех дизъюнкций, в которые входит литерал Z, и удалением его отрицания из всех остальных дизъюнкций). Каждая из полученных формул подвергается некоторым не изменяющим ее выполнимости преобразованиям, производимым за полиномиальное время, таким как удаление 1-дизъюнкций (дизъюнкций, содержащих ровно по одному литералу) и чистых литералов (литерал является чистым, если его отрицание не входит в формулу). Таким образом, алгоритм строит некоторое дерево расщепления, каждый лист которого помечен либо пустой (т.е. тождественно истинной) формулой,

либо формулой, содержащей пустую дизъюнкцию (т.е. тождественно ложной). Если хотя бы в одном из листьев дерева расщепления находится пустая формула, это означает, что исходная формула выполнима.

Алгоритмы из [13] и [12] имеют сложность р{Ь)2м. В начале 80х годов было замечено [27, 2, 3, 29], что выполнимость формул в /г-КНФ можно выяснить быстрее, если переменные для расщепления выбирать из самых коротких дизъюнкций. Таким образом, задача выполнимости для формулы в &-КНФ с N переменными сводится к задаче выполнимости для формул с N — 1, N — 2, ..., N — к + 2 и N — к переменными. Решение соответствующего рекуррентного уравнения дает оценку1 р(Ь)ф{к)н на время работы алгоритма, где ф(к) — единственный положительный корень полинома хк — хк~1 — ... — 1. Впоследствии для формул в 3-КНФ были созданы алгоритмы, работающие время р(Ь)1.579ж [32], р(£)1.571^ [42], р(1,)1.5045* [23]. И.Шиермейер анонсировал оценку р(Ь) 1.497^ [33], но полное доказательство пока не опубликовано. Имеются и работы по понижению экспоненциальных верхних оценок для других КР-полных задач, в частности, для задачи 3-раскрашиваемости графа [8].

В начале 80х годов появились также алгоритмы, для которых приводились верхние оценки относительно количества дизъюнкций в исходной формуле и ее длины. Это алгоритм Б. Мониена и Э. Шпекенмей-ера [28], затрачивающий время р(Ь) 1.2600х, и алгоритм X. Люкхардта [25], затрачивающий время Впоследствии эти алгоритмы

были улучшены О. Кулльманном и X. Люкхардтом [24]: первый алгоритм был значительно упрощен, а вторая оценка была снижена до р(Ь)1.08011. Основная

идея этих алгоритмов — использование расширенного принципа знака. Пусть Р — некоторое свойство, которым может обладать пара из литерала и формулы в КНФ, такое что Р(1, Г)

*В указанных статьях доказывается лучшая оценка, см. табл. I.

выполняется хотя бы для одного из литералов I = V или I = V для каждой переменной г>, встречающейся в формуле Р. Например, Р(1, Р) может означать "литерал I входит в формулу Р не более одного раза".

Расширенный принцип знака. Если в формулу Р не входит ни одной дизъюнкции, состоящей только из литералов, для которых выполняется свойство Р (относительно формулы Р), то формула Р выполнима.

Наиболее простой пример применения этого принципа продемонстрировал X. Люкхардт в [25]. Он рассматривал формулы в КНФ-(1,оо): формула принадлежит этому классу, если для каждой пары противоположных литералов по крайней мере один из них входит в формулу не более одного раза1. В этом случае, если положить Р(/,Р) ="литерал I входит в формулу Р не более одного раза", то расширенный принцип знака позволяет найти в формуле дизъюнкцию {/ь/г, • • ■ состоящую только из литералов, которые не входят более ни в какие дизъюнкции. Задача выполнимости исходной формулы Р таким образом сводится к задаче выполнимости формул з], ь^Дз] и \J21h] (пусть, для простоты, к = 3). В самом деле, не умаляя общности, можно считать, что ровно один из литералов ¿ь/г^з является истинным в выполняющем наборе: в формуле Р[1\] литералы /2 и /3 становятся чистыми и могут быть легко удалены, и т.д. В итоге получается, что задача выполнимости формулы с N переменными сводится к задаче выполнимости к формул с N — к переменными, т.е. время работы этого алгоритма не превосходит

8пр(к1/к)мр{ь) = г^рЩ. к> 1

В статье [24] расширенный принцип знака используется для по-

*В настоящей диссертации используется другое определение: см. раздел 1.2 и сноску на стр. 78.

строения алгоритмов для произвольных формул в КНФ; полученные алгоритмы имеют хорошие оценки на время исполнения относительно длины формулы и количества дизъюнкций в ней. Поясним метод, с помощью которого получена вторая оценка, поскольку сходная техника используется и в данной диссертации. Эта оценка составляет р(Ь)2к/3 « р(Ь) 1.2600х. В качестве преобразований, упрощающих формулу, выбираем удаление 1-дизъюнкций и замену на резольвенты: для некоторой переменной добавляем в формулу все резольвенты по этой переменной и удаляем из формулы дизъюнкции, в которые эта переменная входила. Такое преобразование применяем только в случае, если оно не увеличивает количества дизъюнкций в формуле, в частности, если переменная входит ровно два раза положительно и ровно два раза отрицательно или входит не более одного раза положительно (или отрицательно). Каждая из переменных, остающихся в формуле после этих преобразований, входит в формулу по крайней мере пять раз, причем не менее двух раз положительно и не менее двух раз отрицательно. Если для расщепления каждый раз выбирать переменную, входящую в формулу по крайней мере три раза положительно и по крайней мере три раза отрицательно, каждая из полученных формул будет иметь по крайней мере на три дизъюнкции меньше; соответствующее рекуррентное уравнение имеет решение 21/3, т.е. как раз то, что фигурирует в искомой оценке. В результате остается разобрать случай, когда формула содержит только переменные, входящие ровно два раза положительно и по крайней мере три раза отрицательно (или наоборот). В этом случае расширенный принцип знака гарантирует наличие дизъюнкции, состоящей исключительно из литералов, входящих в формулу ровно два раза. Расщепление по одному из них оказывается также выгодным: если мы полагаем его значение истинным, оставшиеся литералы будут удалены при замене на резольвенты (они теперь встречаются только

один раз в формуле). Можно показать, что корень соответствующего рекуррентного уравнения будет также 21/3.

Последние известные оценки для метода расщеплений на момент написания данной диссертации указаны в табл. I. Все они, кроме результата для формул в &-КНФ, являются наилучшими из известных верхних оценок не только для метода расщеплений, но и для других алгоритмов для задачи выполнимости. Экспериментальные данные указывают на возможность дальнейшего улучшения этих оценок, например, Дж. М. Кроуфорд и Л. Д. Аутон [11] утверждают, что время работы их алгоритма растет приблизительно как 2м!11. Алгоритмы, решающие МАКС-ВЫП при помощи метода расщеплений, также изучались экспериментально: Б. Борчерс и Дж. Фурман [9] показали, что комбинация метода расщеплений с эвристикой поиска локального максимума оказывается довольно эффективной для случайно порожденных формул в 2-КНФ и 3-КНФ.

В данной диссертации предлагается ряд новых алгоритмов для ВЫП, использующих метод расщеплений, и доказываются верхние оценки на время их исполнения "в наихудшем случае". Оценки для задачи выполнимости формулы в КНФ без ограничений оказываются лучше известных ранее, оценки для других классов формул улучшаются за счет сужения этих классов.

В главе 5 показано, что с помощью алгоритма, использующего метод расщеплений, можно за линейное время найти выполняющий набор для формулы в &-КНФ, имеющей много выполняющих наборов (доля выполняющих наборов среди всех наборов — не меньше некоторой константы). Выполняющий набор для такой формулы может быть легко найден с помощью простого вероятностного алгоритма, который вы-

количество дизъюнкций К длина формулы Ь количество переменных ЛГ

КНФ 1.2600^ [28] 1.08011, [24]

к-ШФ ф(к - 1)* [27, 3]

3-КНФ 1.5045^ [23]

КНФ-(1,оо) 1.4423* [25]

КНФ-(1,2) 1.0416х' [24] 1.1299* [24]

3-КНФ-(1,2) 1.1299Л [24]

Таблица I: Наилучшие известные верхние оценки для алгоритмов для задачи ВЫП, использующих метод расщепления (исключая оценки, полученные в данной диссертации). Оценки приведены с точностью до полиномиального сомножителя р(Ь). Величина ф(к) — единственный положит