4817
правок
Максимальная выполнимость формул в 2-КНФ: различия между версиями
Материал из WEGA
Максимальная выполнимость формул в 2-КНФ (посмотреть исходный код)
Версия от 10:41, 29 марта 2025
, 29 март→Далее
Irina (обсуждение | вклад) м (→Далее) |
Irina (обсуждение | вклад) (→Далее) |
||
| Строка 79: | Строка 79: | ||
'''Теорема 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', где и x – переменная. Положим C = | Доказательство (набросок). Заменим элементы <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>. | ||
На следующем шаге выберем такое число x, чтобы из суммы произвольных степеней x было легко определить наибольшую степень x, встречающуюся в сумме; эта наибольшая степень сразу же дает минимум A[i | На следующем шаге выберем такое число <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>. | ||
Суммируя все вышесказанное, AgjB можно вычислить, построив | Суммируя все вышесказанное, AgjB можно вычислить, построив | ||
