Максимальная выполнимость формул в 2-КНФ

Ключевые слова и синонимы

МАКС 2-ВЫП (MAX 2-SAT)

Постановка задачи

В задаче о максимальной выполнимости формул в 2-КНФ (которая далее будет обозначаться как MAX 2-SAT, или МАКС 2-ВЫП) на входе имеется булева формула в конъюнктивной нормальной форме, такая, что каждый дизъюнкт содержит не более двух литералов. Задача заключается в том, чтобы найти такое присваивание переменным формулы, при котором максимальное количество дизъюнктов выполнимы.

MAX 2-SAT представляет собой классическую задачу оптимизации. Гэйри, Джонсоном и Стокмайером [7] было показано, что ее версия с принятием решений (decision version) является NP-полной, что резко отличает ее от задачи 2-КНФ (2-ВЫП), которая решается за линейное время [2]. Чтобы получить представление о сложности проблемы, приведем краткое описание NP-полноты. Можно преобразовать любой экземпляр задачи 3-КНФ F в MAX-экземпляр 2-КНФ F', заменив каждый дизъюнкт F, такой, что:

[math]\displaystyle{ c_i = ( \ell_1 \lor \ell_2 \lor \ell_2) }[/math], где [math]\displaystyle{ \ell_1, \ell_2 }[/math] и [math]\displaystyle{ \ell_3 }[/math] – произвольные литералы, коллекцией дизъюнктов в 2-КНФ

[math]\displaystyle{ (\ell_1), (\ell_2), (\ell_3), (c_i), (\lnot \ell_1 \lor \lnot \ell_2), (\lnot \ell_2 \lor \lnot \ell_3), (\lnot \ell_1 \lor \lnot \ell_3), (\ell_1 \lor c_i), (\ell_2 \lor c_i), (\ell_3 \lor c_i) }[/math]

где [math]\displaystyle{ c_i }[/math] – новая переменная. Верны следующие утверждения:

• Если присваивание делает [math]\displaystyle{ c_i }[/math] выполнимой, то из десяти дизъюнктов коллекции 2-КНФ могут быть выполнимыми ровно семь.

• Если присваивание делает [math]\displaystyle{ c_i }[/math] невыполнимой, то ровно шесть из десяти дизъюнктов коллекции 2-КНФ могут быть выполнимыми.

Если F выполнима, то существует присваивание, делающее выполнимыми 7/10 дизъюнктов в F', в противном случае никакое присваивание не делает выполнимыми более чем 7/10 дизъюнктов в F'. Поскольку задача 3-ВЫП сводится к МАКС 2-ВЫП, из этого следует, что МАКС 2-ВЫП (как задача с принятием решений) NP-полна.

Нотация

КНФ-формула представляется в виде набора дизъюнктов.

Символы [math]\displaystyle{ \mathbb{R} }[/math] и [math]\displaystyle{ \mathbb{Z} }[/math] обозначают множества вещественных и целых чисел, соответственно. Буква [math]\displaystyle{ \omega }[/math] обозначает наименьшее действительное число, такое, что для всех [math]\displaystyle{ \epsilon \gt 0 }[/math] умножение матрицы размера [math]\displaystyle{ n \times n }[/math] над кольцом может быть выполнено за [math]\displaystyle{ О(n^{\omega + \epsilon}) }[/math] кольцевых операций. В настоящее время известно, что [math]\displaystyle{ \omega \lt 2,376 }[/math] [4]. Кольцевое матричное произведение двух матриц A и B обозначается как [math]\displaystyle{ A \times B }[/math].

Пусть A и B – матрицы с элементами из [math]\displaystyle{ \R \cup \{ \infty \} }[/math]. Произведением расстояний между A и B (сокращенно записываемым как [math]\displaystyle{ A \otimes_d B }[/math]) называется матрица C, определяемая по формуле [math]\displaystyle{ C[i, j] = min_{k = 1, ..., n} \{ A[i, k] + B[k, j] \} }[/math].

Что касается m и n, то применительно к графам они обозначают количество ребер и вершин графа, соответственно. В то же время в КНФ-формулах m и n обозначают количество дизъюнктов и переменных, соответственно.

Основные результаты

Основным результатом данной статьи является процедура, решающая задачу MAX 2-SAT за время [math]\displaystyle{ O(m \cdot 2^{\omega n/3}) }[/math]. Метод может быть обобщен для подсчета количества решений любой задачи оптимизации с ограничениями, в которой на одно ограничение приходится не более двух переменных (см. [17]), хотя изложение в данной статье будет несколько отличаться от приведенного в указанном источнике и будет значительно упрощено. Известно несколько других точных алгоритмов для MAX 2-SAT, работающих более эффективно в специальных случаях – например, на разреженных экземплярах задачи [3, 8, 9, 11, 12, 13, 15, 16]. Ниже описана единственная известная на момент написания статьи процедура, выполняемая за время [math]\displaystyle{ O(poly(m) \cdot 2^{\delta n}) }[/math] (при некотором фиксированном [math]\displaystyle{ \delta \lt 1 }[/math]) во всех возможных случаях.

Ключевая идея

Алгоритм производит редукцию от MAX 2-SAT к задаче MAX TRIANGLE, в которой на входе имеется граф с целочисленными весами вершин и ребер, а целью является вывод 3-цикла с максимальным весом. На первый взгляд существование такой редукции кажется странным, поскольку MAX TRIANGLE можно тривиально решить за время [math]\displaystyle{ O(n^3) }[/math], перебрав все возможные 3-циклы. Суть в том, что редукция экспоненциально увеличивает размер задачи: от экземпляра MAX 2-SAT с m дизъюнктами и n переменными к экземпляра MAX TRIANGLE с [math]\displaystyle{ O(2^{2n/3}) }[/math] ребрами, [math]\displaystyle{ O(2^{n/3}) }[/math] вершинами и весами в диапазоне {-m, ..., m}.

Заметим, что если бы задаче MAX TRIANGLE требовалось [math]\displaystyle{ \Theta(n^3) }[/math] времени для решения, то полученный алгоритм для MAX 2-SAT выполнялся бы за время [math]\displaystyle{ \Theta(2^n) }[/math], что сделало бы приведенную выше редукцию бессмысленной. Однако оказалось, что перебор с временем выполнения [math]\displaystyle{ O(n^3) }[/math] для MAX TRIANGLE – не лучшее, что можно сделать: существует алгоритм для решения этой задачи на основе быстрого умножения матриц, работающий за время [math]\displaystyle{ O(W n^{\omega}) }[/math] на графах с весами в диапазоне {-W, ..., W}.

Основной алгоритм

Сначала описывается редукция от MAX 2-SAT к MAX TRIANGLE, согласно которой каждый треугольник веса K в полученном графе находится в взаимно-однозначном соответствии с присваиванием, при котором становятся выполнимыми K дизъюнктов экземпляра MAX 2-SAT. Пусть a, b – вещественные числа, и пусть [math]\displaystyle{ \Z [a, b] := [a, b] \cap \Z }[/math].

Лемма 1. Если задача MAX TRIANGLE на графах с n вершинами и весами из [math]\displaystyle{ \Z [-W, W] }[/math] разрешима за время [math]\displaystyle{ O(f(W) \cdot g(n)) }[/math] для полиномиальных f и g, то MAX 2-SAT разрешима за время [math]\displaystyle{ O(f(m) \cdot g(2^{n/3})) }[/math], где m – количество дизъюнктов, а n – количество переменных.

Доказательство. Пусть C – заданная формула в 2-КНФ. Предположим без потери общности, что n кратно 3. Пусть F – экземпляр задачи MAX 2-SAT. Произвольным образом разобьем n переменных экземпляра F на три множества [math]\displaystyle{ P_1, P_2, P_3 }[/math], каждое из которых содержит n/3 переменных. Для каждого [math]\displaystyle{ P_i }[/math] составим список [math]\displaystyle{ L_i }[/math] из всех [math]\displaystyle{ 2^{n/3} }[/math] присваиваний переменным из [math]\displaystyle{ P_i }[/math].

Определим граф [math]\displaystyle{ G = (V, E) }[/math], где [math]\displaystyle{ V = L_1 \cup L_2 \cup L_3 }[/math] и [math]\displaystyle{ E = \{ (u, v) | u \in P_i, v \in P_j, i \ne j \} }[/math]. Таким образом, G – это полный трехдольный граф с [math]\displaystyle{ 2^{n/3} }[/math] вершинами в каждой доле, и каждая вершина в G соответствует присваиванию n/3 переменным в C. Веса в вершинах и ребрах G распределяются следующим образом. Для вершины v определим w(v) как количество дизъюнктов, выполнимых в результате частичного присваивания, обозначенное как v. Для каждого ребра {u,v} определим [math]\displaystyle{ w(\{u, v\}) = -W_{uv} }[/math], где [math]\displaystyle{ W_{uv} }[/math] – количество дизъюнктов, выполнимых одновременно u и v.

Определим вес треугольника в G как полную сумму всех весов и вершин в треугольнике.

Утверждение 1. Существует взаимно однозначное соответствие между треугольниками веса K в G и присваиваниями переменных, при которых ровно K дизъюнктов в F становятся выполнимыми.

Доказательство. Пусть a – присваивание переменной. Тогда существуют уникальные вершины [math]\displaystyle{ v_1 \in L_1, v_2 \in L_2, v_3 \in L_3 }[/math], такие, что a в точности является конкатенацией [math]\displaystyle{ v_1, v_2, v_3 }[/math] как присваиваний. Более того, любая тройка вершин [math]\displaystyle{ v_1 \in L_1, v_2 \in L_2, v_3 \in L_3 }[/math] соответствует присваиванию. Таким образом, существует взаимно однозначное соответствие между треугольниками в G и присваиваниями в F.

Количество дизъюнктов, которые становятся выполнимыми при этом присваивании, в точности равно весу соответствующего треугольника. Чтобы убедиться в этом, обозначим за [math]\displaystyle{ T_a = \{ v_1, v_2, v_3 \} }[/math] треугольник в G, соответствующий присваиванию a. Тогда

[math]\displaystyle{ w(T_a) = w(v_1) + w(v_2) + w(v_3) + w( \{v_1, v_2 \}) + w( \{v_2, v_3 \}) + w( \{ v_1, v_3 \}) = \sum_{i = 1}^3 | \{ c \in F | v_i }[/math] выполним при [math]\displaystyle{ F \} | - \sum_{i, j: i \ne j} | \{ c \in F | v_i, v_j }[/math] выполнимы при [math]\displaystyle{ F \} | = | \{ c \in F | a }[/math] выполнимо при [math]\displaystyle{ F \} | }[/math],

где последнее равенство следует из принципа включения-исключения. □

Заметим, что количество вершин в G равно [math]\displaystyle{ 3 \cdot 2^{n/3} }[/math], а абсолютное значение веса любой вершины и любого ребра равно m. Поэтому, запустив на G алгоритм MAX TRIANGLE, решение MAX 2-SAT можно получить за время [math]\displaystyle{ O(f(m) \cdot g(3 \cdot 2^{n/3})) }[/math], что соответствует [math]\displaystyle{ O(f(m) \cdot g(2^{n/3})) }[/math] в силу полиномиальности g. Этим завершается доказательство леммы 1. □

Далее

описывается процедура нахождения максимального треугольника быстрее, чем с помощью простого перебора, с использованием быстрого умножения матриц. Алон, Галил и Маргалит [1] (вслед за Ювалем [20]) показали, что произведение расстояний для матриц с элементами из [math]\displaystyle{ \Z [-W, W] }[/math] может быть вычислено с помощью быстрого умножения матриц в качестве подпрограммы.

Теорема 2 (Алон, Галил, Маргалит [1]). Пусть A и B – матрицы размера n x n с элементами из [math]\displaystyle{ \Z [-W, W] \cup{ \infty} }[/math]. Тогда произведение [math]\displaystyle{ A \otimes_d B }[/math] может быть вычислено за время [math]\displaystyle{ O(W \; n^{\omega} \; log \; n) }[/math].

Доказательство (набросок). Заменим элементы [math]\displaystyle{ \infty }[/math] в A и B на 2W + 1 следующим образом. Определим матрицы A' и B', где [math]\displaystyle{ A'[i, j] = x^{3W - A[i, j]}, B'[i, j] = x^{3W - B[i, j]} }[/math] и [math]\displaystyle{ x }[/math] – переменная. Положим [math]\displaystyle{ C = A' \times B' }[/math]. Тогда [math]\displaystyle{ C[i, j] = \sum_{k = 1}^n x^{6W - A[i, k] - B[k, j]} }[/math].

На следующем шаге выберем такое число [math]\displaystyle{ x }[/math], чтобы из суммы произвольных степеней [math]\displaystyle{ x }[/math] было легко определить наибольшую степень [math]\displaystyle{ x }[/math], встречающуюся в сумме; эта наибольшая степень сразу же дает минимум [math]\displaystyle{ A[i, k] + B[k, j] }[/math]. Каждый [math]\displaystyle{ C[i,j] }[/math] – это полином от [math]\displaystyle{ x }[/math] с коэффициентами из [math]\displaystyle{ \Z [0, n] }[/math]. Предположим, что каждый [math]\displaystyle{ C[i, j] }[/math] оценивается при [math]\displaystyle{ x = n + 1 }[/math]. Тогда каждый элемент [math]\displaystyle{ C[i, j] }[/math] можно рассматривать как (n + 1)-арное число, а положение старшей значащей цифры этого числа дает минимум [math]\displaystyle{ A[i, k] + B[k, j] }[/math].

Суммируя все вышесказанное, [math]\displaystyle{ A \otimes_d B }[/math] можно вычислить, построив [math]\displaystyle{ A'[i, j] = (n + 1)^{3W-A[i, j]]}, B'[i, j] = (n + 1)^{3w - B[i, j]} }[/math] за время O(W log n) на каждый элемент, вычисляя [math]\displaystyle{ C = A' \times B' }[/math] за время [math]\displaystyle{ O(n^{\omega} \cdot (W \; log \; n)) }[/math] (так как размеры элементов равны O(W log n)), а затем извлекая минимум из каждого элемента [math]\displaystyle{ C }[/math] за время [math]\displaystyle{ O(n^2 \cdot W \; log \; n) }[/math]. Заметим, что если минимум для элемента [math]\displaystyle{ C[i,j] }[/math] равен хотя бы [math]\displaystyle{ 2W + 1 }[/math], то [math]\displaystyle{ C[i, j] = \infty }[/math]. □

Используя быстрый алгоритм произведения расстояний, можно решить задачу MAX TRIANGLE быстрее, чем простым перебором. Нижеследующее изложение основывается на алгоритм Итаи и Роде [10] для выявления наличия треугольника в невзвешенном графе менее чем за [math]\displaystyle{ n^3 }[/math] шагов. Результат может быть обобщен на подсчет количества k-клик для произвольного [math]\displaystyle{ k \ge 3 }[/math]. (Для простоты изложения результат подсчета опущен. Что касается работы с k-кликами, то, к сожалению, не существует асимптотического преимущества во времени выполнения от использования алгоритма на k-кликах вместо алгоритма на треугольниках – по крайней мере, если говорить о лучших на сегодня алгоритмах для решения этих задач).

Теорема 3. Задача MAX TRIANGLE может быть решена за время [math]\displaystyle{ O(W \; n^{\omega} \; log \; n) }[/math] для графов с весами из [math]\displaystyle{ \Z [-W, W] }[/math].

Доказательство. Сначала демонстрируется, что весовая функция на вершинах и ребрах может быть преобразована в эквивалентную весовую функцию с весами только на ребрах. Пусть w – весовая функция над G. Переопределим веса следующим образом:

[math]\displaystyle{ w'( \{ u, v \}) = \frac{w(u) + w(v)}{2} + w( \{u, v \}), w'(u) = 0 }[/math].

Обратите внимание, что вес треугольника при такой редукции остается неизменным.

Следующим шагом будет использование быстрого произведения расстояний для поиска треугольника с максимальным весом в реберно-взвешенном графе с n вершинами. Рассмотрим множество вершин G как множество {1, ..., n}. Определим A как матрицу размера n x n, такую, что A[i, j] = - w({i, j}), если существует ребро {i, j}, и A[i, j] = [math]\displaystyle{ \infty }[/math] в противном случае. Утверждение заключается в том, что треугольник с весом не менее K включает вершину i тогда и только тогда, когда [math]\displaystyle{ (A \otimes_d B \; A \otimes_d A) [i, j] \le -K }[/math]. Это объясняется тем, что данное неравенство выполняется тогда и только тогда, когда существуют отличные друг от друга j и k, такие, что {i, j}, {j, k}, {k, i} – ребра, и A[i, j] + A[j, k] + A[k, i] [math]\displaystyle{ \le }[/math] -K, то есть w({i, j}) + w({j, k}) + w({k, i}) [math]\displaystyle{ \ge }[/math] K.

Поэтому, найдя i, такой, что [math]\displaystyle{ (A \otimes_d B \; A \otimes_d A) [i, j] }[/math] минимизировано, мы получим вершину i, содержащуюся в максимальном треугольнике. Для получения фактического треугольника следует проверить все m ребер {j, k} на предмет того, является ли {i, j, k} треугольником. □

Теорема 4. Задачу MAX 2-SAT можно решить за время [math]\displaystyle{ O(m \cdot 1,732^n) }[/math].

Доказательство. Пусть дан набор дизъюнктов C. Применим редукцию из леммы 1, чтобы получить граф G с [math]\displaystyle{ O(2^{n/3}) }[/math] вершинами и весами из [math]\displaystyle{ \Z [-m, m] }[/math]. Применим алгоритм из Теоремы 3 для вывода максимального треугольника в G за время [math]\displaystyle{ O(m \cdot 2^{\omega n/3} \; log(2^{n/3})) = O(m \cdot 1,732^n) }[/math], используя [math]\displaystyle{ O(n^{2,376}) }[/math] операций матричного умножения Копперсмита-Винограда [[1]] [4]. □

Применение

Модифицировав конструкцию графа, можно решать другие задачи за время O(1.732n), такие как MAX CUT (максимальный разрез), MINIMUM BISECTION (минимальная бисекция) и SPARSEST CUT (самое неплотное сечение). В целом, любая задача оптимизации с ограничениями, в которой каждое ограничение имеет не более двух переменных, может быть решена быстрее с помощью описанного выше подхода. Более подробную информацию можно найти в [ ] и в недавнем обзоре Вёгингера [19]. Схожая с вышеприведенным алгоритмом техника была также использована Дорном [6] с целью ускорения динамического программирования для некоторых задач на планарных графах (и вообще на графах с ограниченной путевой шириной).

Открытые вопросы

• Необходимо улучшить использование памяти описанным выше алгоритмом. В настоящее время он требует @(22"/3). Очень интересен пока нерешенный вопрос: существует ли алгоритм для MAX 2-SAT со временем O(1,99n), использующий только полиномиальный объем памяти. На этот вопрос можно было бы ответить положительно, если бы удалось найти алгоритм решения задачи о k-кликах (k-CLIQUE) с полилогарифмическими затратами памяти и временем nk~ для некоторых S > 0 и k > 3.

• Хотелось бы найти алгоритм для MAX 2-SAT, работающий быстрее 2n и не требующий быстрого умножения матриц. Алгоритмы быстрого умножения матриц имеют печальную репутацию непрактичных.

• Следует обобщить вышеприведенный алгоритм для задачи MAX k-SAT, где k – любое целое положительное число. В текущей формулировке требуется эффективный алгоритм для нахождения малой гиперклики в гиперграфе. Однако для этой задачи неизвестны какие-либо результаты общего вида. Есть гипотеза, что для всех k > 2 MAX k-SAT решается за время 6(2"'1~*+T-)), исходя из предположения, что умножение матриц выполняется за время n2+o(1) [17].

См. также

• Алгоритм поиска кратчайших путей при помощи матричного произведения
• Максимальный разрез
• Минимальная бисекция
• Самое неплотное сечение

Литература

1. Alon, N., Galil, Z., Margalit, O.: On the exponent of the all-pairs shortest path problem. J. Comput. Syst. Sci. 54,255-262 (1997)

2. Aspvall, B., Plass, M.F., Tarjan R.E.: A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Proc. Lett. 8(3),121-123(1979)

3. Bansal, N., Raman, V.: Upper bounds for Max Sat: Further Improved. In: Proceedings of ISAAC. LNCS, vol. 1741, pp. 247-258. Springer, Berlin (1999)

4. Coppersmith, D., Winograd S.: Matrix Multiplication via Arithmetic Progressions. JSC 9(3), 251-280 (1990)

5. Dantsin, E., Wolpert, A.: Max SAT for formulas with constant clause density can be solved faster than in O(2n) time. In: Proc. of the 9th International Conference on Theory and Applications of Satisfiability Testing. LNCS, vol. 4121, pp. 266-276. Springer, Berlin (2006)

6. Dorn, F.: Dynamic Programming and Fast Matrix Multiplication. In: Proceedings of 14th Annual European Symposium on Algorithms. LNCS, vol.4168, pp. 280-291. Springer, Berlin (2006)

7. Garey, M., Johnson, D., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1, 237-267 (1976)

8. Gramm, J., Niedermeier, R.: Faster exact solutions for Max2Sat. In: Proceedings of CIAC. LNCS, vol. 1767, pp. 174-186. Springer, Berlin (2000)

9. Hirsch, E.A.: A 2m/4-time Algorithm for Max 2-SAT: Corrected Version. Electronic Colloquium on Computational Complexity Report TR99-036 (2000)

10. Itai, A., Rodeh, M.: Finding a Minimum Circuit in a Graph. SIAM J. Comput. 7(4), 413^23 (1978)

11. Kneis, J., Molle, D., Richter, S., Rossmanith, P.: Algorithms Based on the Treewidth of Sparse Graphs. In: Proc. Workshop on Graph Theoretic Concepts in Computer Science. LNCS, vol. 3787, pp. 385-396. Springer, Berlin (2005)

12. Kojevnikov, A., Kulikov, A.S.: A New Approach to Proving Up per Bounds for Max 2-SAT. In: Proc. of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 11 -17 (2006)

13. Mahajan, M., Raman, V.: Parameterizing above Guaranteed Values: MAXSAT and MAXCUT. J. Algorithms 31(2), 335-354 (1999)

14. Niedermeier, R., Rossmanith, P.: New upper bounds for maximum satisfiability. J. Algorithms 26,63-88 (2000)

15. Scott, A., Sorkin, G.: Faster Algorithms for MAX CUT and MAX CSP, with Polynomial Expected Time for Sparse Instances. In: Proceedings of RANDOM-APPROX 2003. LNCS, vol. 2764, pp. 382-395. Springer, Berlin (2003)

16. Williams, R.:On Computing k-CNF Formula Properties. In: Theory and Applications of Satisfiability Testing. LNCS, vol. 2919, pp. 330-340. Springer, Berlin (2004)

17. Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(2-3), 357-365 (2005)

18. Woeginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: Combinatorial Optimization-Eureka! You shrink! LNCS, vol. 2570, pp. 185-207. Springer, Berlin (2003)

19. Woeginger, G.J.: Space and time complexity of exact algorithms: some open problems. In: Proc. 1st Int. Workshop on Parameterized and Exact Computation (IWPEC 2004). LNCS, vol. 3162, pp. 281-290. Springer, Berlin (2004)

20. Yuval, G.: An Algorithm for Finding All Shortest Paths Using N2.81 Infinite-Precision Multiplications. Inf. Process. Lett. 4(6), 155-156(1976)