4622
правки
Максимальная выполнимость формул в 2-КНФ: различия между версиями
Материал из WEGA
Максимальная выполнимость формул в 2-КНФ (посмотреть исходный код)
Версия от 10:49, 27 марта 2025
, 27 март→Далее
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Далее) |
||
| Строка 74: | Строка 74: | ||
== Далее == | == Далее == | ||
описывается процедура нахождения максимального треугольника быстрее, чем с помощью простого перебора, с использованием быстрого умножения матриц. Алон, Галил и Маргалит [ ] (вслед за Ювалем [20]) показали, что произведение расстояний для матриц с элементами из Z[- W | описывается процедура нахождения максимального треугольника быстрее, чем с помощью простого перебора, с использованием быстрого умножения матриц. Алон, Галил и Маргалит [1] (вслед за Ювалем [20]) показали, что произведение расстояний для матриц с элементами из <math>\Z [-W, W]</math> может быть вычислено с помощью быстрого умножения матриц в качестве подпрограммы. | ||
Теорема 2 (Алон, Галил, Маргалит [ ]). Пусть A и B – матрицы размера n x n с элементами из Z | '''Теорема 2 (Алон, Галил, Маргалит [1]). Пусть A и B – матрицы размера n x n с элементами из <math>\Z [-W, W] \cup{ \infty}</math>. Тогда произведение A ®d B может быть вычислено за время O(Wn! log n).''' | ||
Доказательство (набросок). Заменим 1 запись в A и B на 2W + 1 следующим образом. Определим матрицы A0 и B0, где и x – переменная. Положим C = A0 x B0. Тогда | Доказательство (набросок). Заменим 1 запись в A и B на 2W + 1 следующим образом. Определим матрицы A0 и B0, где и x – переменная. Положим C = A0 x B0. Тогда | ||
