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

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

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