4652
правки
Максимальная выполнимость формул в 2-КНФ: различия между версиями
Материал из WEGA
Максимальная выполнимость формул в 2-КНФ (посмотреть исходный код)
Версия от 10:37, 27 марта 2025
, 27 март→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 49: | Строка 49: | ||
'''Лемма 1'''. Если задача MAX TRIANGLE на графах с n вершинами и весами из <math>\Z [-W, W]</math> разрешима за время O(f(W) | '''Лемма 1'''. Если задача MAX TRIANGLE на графах с n вершинами и весами из <math>\Z [-W, W]</math> разрешима за время <math>O(f(W) \cdot g(n))</math> для полиномиальных f и g, то MAX 2-SAT разрешима за время <math>O(f(m) \cdot g(2^{n/3}))</math>, где m – количество дизъюнктов, а n – количество переменных. | ||
Доказательство. Пусть C – заданная формула в 2-КНФ. Предположим без потери общности, что n кратно 3. Пусть F – экземпляр задачи MAX 2-SAT. Произвольным образом разобьем n переменных экземпляра F на три множества | '''Доказательство'''. Пусть C – заданная формула в 2-КНФ. Предположим без потери общности, что n кратно 3. Пусть F – экземпляр задачи MAX 2-SAT. Произвольным образом разобьем n переменных экземпляра F на три множества <math>P_1, P_2, P_3</math>, каждое из которых содержит n/3 переменных. Для каждого <math>P_i</math> составим список <math>L_i</math> из всех <math>2^{n/3}</math> присваиваний переменным из <math>P_i</math>. | ||
Определим граф G = (V, E), где V = | Определим граф <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. | ||
| Строка 60: | Строка 60: | ||
Утверждение 1. Существует взаимно однозначное соответствие между треугольниками веса K в G и присваиваниями переменных, при которых ровно K дизъюнктов в F становятся выполнимыми. | '''Утверждение 1'''. Существует взаимно однозначное соответствие между треугольниками веса K в G и присваиваниями переменных, при которых ровно K дизъюнктов в F становятся выполнимыми. | ||
Доказательство. Пусть a – присваивание переменной. Тогда существуют единственные узлы v1 2 L1; v2 2 L2 и v3 2 L3 такие, что a в точности является конкатенацией v1, v2, v3 как присваиваний. Более того, любая тройка вершин v1 2 L1, v2 2 L2 и v3 2 L3 соответствует присваиванию. Таким образом, существует взаимно однозначное соответствие между треугольниками в G и присваиваниями в F. | Доказательство. Пусть a – присваивание переменной. Тогда существуют единственные узлы v1 2 L1; v2 2 L2 и v3 2 L3 такие, что a в точности является конкатенацией v1, v2, v3 как присваиваний. Более того, любая тройка вершин v1 2 L1, v2 2 L2 и v3 2 L3 соответствует присваиванию. Таким образом, существует взаимно однозначное соответствие между треугольниками в G и присваиваниями в F. | ||
