4640
правок
Максимальная выполнимость формул в 2-КНФ: различия между версиями
Перейти к навигации
Перейти к поиску
м
Максимальная выполнимость формул в 2-КНФ (посмотреть исходный код)
Версия от 10:51, 27 марта 2025
, 27 март→Далее
Irina (обсуждение | вклад) м (→Далее) |
Irina (обсуждение | вклад) м (→Далее) |
||
| Строка 77: | Строка 77: | ||
'''Теорема 2 (Алон, Галил, Маргалит [1]). Пусть A и B – матрицы размера n x n с элементами из <math>\Z [-W, W] \cup{ \infty}</math>. Тогда произведение A | '''Теорема 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 = A0 x B0. Тогда | ||
На следующем шаге выберем такое число x, чтобы из суммы произвольных степеней x было легко определить наибольшую степень x, встречающуюся в сумме; эта наибольшая степень сразу же дает минимум A[i; k] + B[k; j]. Каждый C[i,j] – это полином от x с коэффициентами из Z[0; n]. Предположим, что каждый C[i,j] оценивается при x = (n + 1). Тогда каждый элемент C[i,j] можно рассматривать как (n + 1)-арное число, а положение старшей значащей цифры этого числа дает минимум A[i; k] + B[k;j]. | На следующем шаге выберем такое число x, чтобы из суммы произвольных степеней x было легко определить наибольшую степень x, встречающуюся в сумме; эта наибольшая степень сразу же дает минимум A[i; k] + B[k; j]. Каждый C[i,j] – это полином от x с коэффициентами из Z[0; n]. Предположим, что каждый C[i,j] оценивается при x = (n + 1). Тогда каждый элемент C[i,j] можно рассматривать как (n + 1)-арное число, а положение старшей значащей цифры этого числа дает минимум A[i; k] + B[k;j]. | ||