4817
правок
Максимальная выполнимость формул в 2-КНФ: различия между версиями
Перейти к навигации
Перейти к поиску
м
Максимальная выполнимость формул в 2-КНФ (посмотреть исходный код)
Версия от 04:11, 3 апреля 2025
, 3 апрель→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 46: | Строка 46: | ||
'''Основной алгоритм''' | '''Основной алгоритм''' | ||
Сначала описывается редукция от MAX 2-SAT к MAX TRIANGLE, согласно которой каждый треугольник веса K в полученном графе находится в взаимно | Сначала описывается редукция от MAX 2-SAT к MAX TRIANGLE, согласно которой каждый треугольник веса K в полученном графе находится в взаимно однозначном соответствии с присваиванием, при котором становятся выполнимыми K дизъюнктов экземпляра MAX 2-SAT. Пусть a, b – вещественные числа, и пусть <math>\Z [a, b] := [a, b] \cap \Z</math>. | ||
| Строка 58: | Строка 58: | ||
'''Утверждение 1'''. Существует взаимно однозначное соответствие между треугольниками веса K в G и присваиваниями переменных, при которых ровно K дизъюнктов в F становятся выполнимыми. | '''Утверждение 1'''. Существует взаимно однозначное соответствие между треугольниками веса K в графе G и присваиваниями переменных, при которых ровно K дизъюнктов в F становятся выполнимыми. | ||
Доказательство. Пусть ''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. | Доказательство. Пусть ''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. | ||
| Строка 75: | Строка 75: | ||
'''Теорема 2 (Алон, Галил, Маргалит [1]). Пусть A и B – матрицы размера n x n с элементами из <math>\Z [-W, W] \cup{ \infty}</math>. Тогда произведение <math>A \otimes_d B</math> может быть вычислено за время <math>O(W \; n^{\omega} \; log \; n)</math>.''' | '''Теорема 2 (Алон, Галил, Маргалит [1]). Пусть A и B – матрицы размера n x n с элементами из <math>\Z [-W, W] \cup \{ \infty \}</math>. Тогда произведение <math>A \otimes_d B</math> может быть вычислено за время <math>O(W \; n^{\omega} \; log \; n)</math>.''' | ||
Доказательство (набросок). Заменим элементы <math>\infty</math> в A и B на 2W + 1 следующим образом. Определим матрицы A' и B', где <math>A'[i, j] = x^{3W - A[i, j]}, B'[i, j] = x^{3W - B[i, j]}</math> и <math>x</math> – переменная. Положим <math>C = A' \times B'</math>. Тогда <math>C[i, j] = \sum_{k = 1}^n x^{6W - A[i, k] - B[k, j]}</math>. | Доказательство (набросок). Заменим элементы "<math>\infty</math>" в A и B на 2W + 1 следующим образом. Определим матрицы A' и B', где <math>A'[i, j] = x^{3W - A[i, j]}, B'[i, j] = x^{3W - B[i, j]}</math> и <math>x</math> – переменная. Положим <math>C = A' \times B'</math>. Тогда <math>C[i, j] = \sum_{k = 1}^n x^{6W - A[i, k] - B[k, j]}</math>. | ||
На следующем шаге выберем такое число <math>x</math>, чтобы из суммы произвольных степеней <math>x</math> было легко определить наибольшую степень <math>x</math>, встречающуюся в сумме; эта наибольшая степень сразу же дает минимум <math>A[i, k] + B[k, j]</math>. Каждый <math>C[i,j]</math> | На следующем шаге выберем такое число <math>x</math>, чтобы из суммы произвольных степеней <math>x</math> было легко определить наибольшую степень <math>x</math>, встречающуюся в сумме; эта наибольшая степень сразу же дает минимум <math>A[i, k] + B[k, j]</math>. Каждый элемент <math>C[i,j]</math> представляет собой полином от <math>x</math> с коэффициентами из <math>\Z [0, n]</math>. Предположим, что каждый <math>C[i, j]</math> оценивается при <math>x = n + 1</math>. Тогда каждый элемент <math>C[i, j]</math> можно рассматривать как (n + 1)-арное число, а положение старшей значащей цифры этого числа дает минимум <math>A[i, k] + B[k, j]</math>. | ||
Суммируя все вышесказанное, <math>A \otimes_d B</math> можно вычислить, построив <math>A'[i, j] = (n + 1)^{3W-A[i, j | Суммируя все вышесказанное, <math>A \otimes_d B</math> можно вычислить, построив <math>A'[i, j] = (n + 1)^{3W-A[i, j]}, B'[i, j] = (n + 1)^{3w - B[i, j]}</math> за время O(W log n) на каждый элемент, вычисляя <math>C = A' \times B'</math> за время <math>O(n^{\omega} \cdot (W \; log \; n))</math> (так как размеры элементов равны O(W log n)), а затем извлекая минимум из каждого элемента <math>C</math> за время <math>O(n^2 \cdot W \; log \; n)</math>. Заметим, что если минимум для элемента <math>C[i,j]</math> равен хотя бы <math>2W + 1</math>, то <math>C[i, j] = \infty</math>. □ | ||
Используя быстрый алгоритм произведения расстояний, можно решить задачу MAX TRIANGLE быстрее, чем простым перебором. Нижеследующее изложение основывается на | Используя быстрый алгоритм произведения расстояний, можно решить задачу MAX TRIANGLE быстрее, чем простым перебором. Нижеследующее изложение основывается на алгоритме Итаи и Роде [10] для выявления наличия треугольника в невзвешенном графе менее чем за <math>n^3</math> шагов. Результат может быть обобщен на ''подсчет'' количества [[Задача о клике|k-клик]] для произвольного <math>k \ge 3</math>. (Для простоты изложения результат подсчета опущен. Что касается работы с k-кликами, то, к сожалению, не существует асимптотического преимущества во времени выполнения от использования алгоритма на k-кликах вместо алгоритма на треугольниках – по крайней мере, если говорить о лучших на сегодня алгоритмах для решения этих задач). | ||