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

Суммируя все вышесказанное, <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 быстрее, чем простым перебором. Нижеследующее изложение основывается на алгоритм Итаи и Роде [10] для выявления наличия треугольника в невзвешенном графе менее чем за <math>n^3</math> шагов. Результат может быть обобщен на ''подсчет'' количества [[Задача о клике|k-клик]] для произвольного <math>k \ge 3</math>. (Для простоты изложения результат подсчета опущен. Что касается работы с k-кликами, то, к сожалению, не существует асимптотического преимущества во времени выполнения от использования алгоритма на k-кликах вместо алгоритма на треугольниках – по крайней мере, если говорить о лучших на сегодня алгоритмах для решения этих задач).

'''Теорема 3. Задача MAX TRIANGLE может быть решена за время <math>O(W \; n^{\omega} \; log \; n)</math> для графов с весами из <math>\Z [-W, W]</math>.'''

Следующим шагом будет использование быстрого произведения расстояний для поиска треугольника с максимальным весом в реберно-взвешенном графе с n вершинами. Рассмотрим множество вершин G как множество {1, ..., n}. Определим A как матрицу размера n x n, такую, что A[i, j] = - w({i, j}), если существует ребро {i, j}, и A[i, j] = <math>\infty</math> в противном случае. Утверждение заключается в том, что треугольник с весом не менее K включает вершину i тогда и только тогда, когда (A ®d A ®d A)[i; i] < -K. Это объясняется тем, что (A ®д A Cg)^ A)[i; i] < -K тогда и только тогда, когда существуют отличные j и k такие, что fi; jg; fj; kg; fk; ig – ребра и A[i;j] + A[j;k] + A[k;i] < -K, т.е. w(fi;jg) + w(fj;kg) + w({k,i})>K.