4622
правки
Максимальная выполнимость формул в 2-КНФ: различия между версиями
Материал из WEGA
Максимальная выполнимость формул в 2-КНФ (посмотреть исходный код)
Версия от 10:31, 27 марта 2025
, 27 март→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 41: | Строка 41: | ||
Заметим, что если бы задаче MAX TRIANGLE требовалось | Заметим, что если бы задаче MAX TRIANGLE требовалось <math>\Theta(n^3)</math> времени для решения, то полученный алгоритм для MAX 2-SAT выполнялся бы за время <math>\Theta(2^n)</math>, что сделало бы приведенную выше редукцию бессмысленной. Однако оказалось, что перебор с временем выполнения <math>O(n^3)</math> для MAX TRIANGLE – не лучшее, что можно сделать: существует алгоритм для решения этой задачи на основе быстрого умножения матриц, работающий за время <math>O(W n^{\omega})</math> на графах с весами в диапазоне {-W, ..., W}. | ||
'''Основной алгоритм''' | '''Основной алгоритм''' | ||
Сначала описывается редукция от MAX 2-SAT к MAX TRIANGLE, согласно которой каждый треугольник веса K в полученном графе находится в взаимно-однозначном соответствии с присваиванием, при котором становятся выполнимыми K дизъюнктов экземпляра MAX 2-SAT. Пусть a, b – вещественные числа, и пусть Z[a | Сначала описывается редукция от MAX 2-SAT к MAX TRIANGLE, согласно которой каждый треугольник веса K в полученном графе находится в взаимно-однозначном соответствии с присваиванием, при котором становятся выполнимыми K дизъюнктов экземпляра MAX 2-SAT. Пусть a, b – вещественные числа, и пусть <math>\Z [a, b] := [a, b] \cap \Z</math>. | ||
Лемма 1. Если задача MAX TRIANGLE на графах с n вершинами и весами из Z | '''Лемма 1'''. Если задача MAX TRIANGLE на графах с n вершинами и весами из <math>\Z [-W, W]</math> разрешима за время O(f(W) ■ g(n)) для полиномиальных f и g, то MAX 2-SAT разрешима за время O(f(m) - g(2n/3)), где m – количество дизъюнктов, а n – количество переменных. | ||
Доказательство. Пусть C – заданная формула в 2-КНФ. Предположим без потери общности, что n кратно 3. Пусть F – экземпляр задачи MAX 2-SAT. Произвольным образом разобьем n переменных экземпляра F на три множества P1, P2, P3, каждое из которых содержит n/3 переменных. Для каждого Pi составим список Li из всех 2n/3 присваиваний переменным из Pi. | Доказательство. Пусть C – заданная формула в 2-КНФ. Предположим без потери общности, что n кратно 3. Пусть F – экземпляр задачи MAX 2-SAT. Произвольным образом разобьем n переменных экземпляра F на три множества P1, P2, P3, каждое из которых содержит n/3 переменных. Для каждого Pi составим список Li из всех 2n/3 присваиваний переменным из Pi. | ||
