4640
правок
Максимальная выполнимость формул в 2-КНФ: различия между версиями
Материал из WEGA
Максимальная выполнимость формул в 2-КНФ (посмотреть исходный код)
Версия от 10:47, 27 марта 2025
, 27 март→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 71: | Строка 71: | ||
Заметим, что количество вершин в G равно 3 | Заметим, что количество вершин в G равно <math>3 \cdot 2^{n/3}</math>, а абсолютное значение веса любой вершины и любого ребра равно m. Поэтому, запустив на G алгоритм MAX TRIANGLE, решение MAX 2-SAT можно получить за время <math>O(f(m) \cdot g(3 \cdot 2^{n/3}))</math>, что соответствует <math>O(f(m) \cdot g(2^{n/3}))</math> в силу полиномиальности g. Этим завершается доказательство леммы 1. □ | ||
== Далее == | == Далее == | ||
