Максимальная выполнимость формул в 2-КНФ: различия между версиями

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

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

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

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

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

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

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

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

 

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

 

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

== Далее ==

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

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

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

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

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

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

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

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

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

Теорема 4. Задачу MAX 2-SAT можно решить за время O(m ■ 1:732n).

Доказательство. Пусть дан набор дизъюнктов C. Применим редукцию из леммы 1, чтобы получить граф G с O(2n/3) вершинами и весами из Ъ\-т, m]. Применим алгоритм из Теоремы 3 для вывода максимального треугольника в G за время O(m ■ 2!n/3 log(2n/3)) =

O(m - 1:732n), используя O(n2.376) матричное умножение Копперсмита-Винограда [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].

* [[Самое неплотное сечение]]