4632
правки
Максимальная выполнимость формул в 2-КНФ: различия между версиями
Материал из WEGA
Максимальная выполнимость формул в 2-КНФ (посмотреть исходный код)
Версия от 10:46, 27 марта 2025
, 27 март→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 62: | Строка 62: | ||
'''Утверждение 1'''. Существует взаимно однозначное соответствие между треугольниками веса K в G и присваиваниями переменных, при которых ровно K дизъюнктов в F становятся выполнимыми. | '''Утверждение 1'''. Существует взаимно однозначное соответствие между треугольниками веса K в G и присваиваниями переменных, при которых ровно K дизъюнктов в F становятся выполнимыми. | ||
Доказательство. Пусть a – присваивание переменной. Тогда существуют | Доказательство. Пусть ''a'' – присваивание переменной. Тогда существуют уникальные вершины <math>v_1 \in L_1, v_2 \in L_2, v_3 \in L_3</math>, такие, что ''a'' в точности является конкатенацией <math>v_1, v_2, v_3</math> как присваиваний. Более того, любая тройка вершин <math>v_1 \in L_1, v_2 \in L_2, v_3 \in L_3</math> соответствует присваиванию. Таким образом, существует взаимно однозначное соответствие между треугольниками в G и присваиваниями в F. | ||
Количество дизъюнктов, которые становятся выполнимыми при этом присваивании, в точности равно весу соответствующего треугольника. Чтобы убедиться в этом, обозначим за | Количество дизъюнктов, которые становятся выполнимыми при этом присваивании, в точности равно весу соответствующего треугольника. Чтобы убедиться в этом, обозначим за <math>T_a = \{ v_1, v_2, v_3 \}</math> треугольник в G, соответствующий присваиванию ''a''. Тогда | ||
<math>w(T_a) = w(v_1) + w(v_2) + w(v_3) + w( \{v_1, v_2 \}) + w( \{v_2, v_3 \}) + w( \{ v_1, v_3 \}) = \sum_{i = 1}^3 | \{ c \in F | v_i</math> выполним при <math> F \} | - \sum_{i, j: i \ne j} | \{ c \in F | v_i, v_j</math> выполнимы при <math> F \} | = | \{ c \in F | a</math> выполнимо при <math> F \} |</math>, | |||
где последнее равенство следует из принципа включения-исключения. □ | где последнее равенство следует из принципа включения-исключения. □ | ||
| Строка 72: | Строка 74: | ||
Далее описывается процедура нахождения максимального треугольника быстрее, чем с помощью простого перебора, с использованием быстрого умножения матриц. Алон, Галил и Маргалит [ ] (вслед за Ювалем [20]) показали, что произведение расстояний для матриц с элементами из Z[- W; W] может быть вычислено с помощью быстрого умножения матриц в качестве подпрограммы. | == Далее == | ||
описывается процедура нахождения максимального треугольника быстрее, чем с помощью простого перебора, с использованием быстрого умножения матриц. Алон, Галил и Маргалит [ ] (вслед за Ювалем [20]) показали, что произведение расстояний для матриц с элементами из Z[- W; W] может быть вычислено с помощью быстрого умножения матриц в качестве подпрограммы. | |||
