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

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

Доказательство. Пусть дан набор дизъюнктов C. Применим редукцию из леммы 1, чтобы получить граф G с <math>O(2^{n/3})</math> вершинами и весами из <math>\Z [-m, m]</math>. Применим алгоритм из Теоремы 3 для вывода максимального треугольника в G за время <math>O(m \cdot 2^{\omega n/3} \; log(2^{n/3})) = O(m \cdot 1,732^n)</math>, используя <math>O(n^{2,376})</math> операций матричного умножения Копперсмита-Винограда [[https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%BE%D0%BF%D0%BF%D0%B5%D1%80%D1%81%D0%BC%D0%B8%D1%82%D0%B0_%E2%80%94_%D0%92%D0%B8%D0%BD%D0%BE%D0%B3%D1%80%D0%B0%D0%B4%D0%B0|Копперсмита-Винограда]] [4]. □