4652
правки
Максимальная выполнимость формул в 2-КНФ: различия между версиями
Материал из WEGA
Максимальная выполнимость формул в 2-КНФ (посмотреть исходный код)
Версия от 07:36, 31 марта 2025
, 31 мартнет описания правки
Irina (обсуждение | вклад) (→Далее) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 73: | Строка 73: | ||
Заметим, что количество вершин в G равно <math>3 \cdot 2^{n/3}</math>, а абсолютное значение веса любой вершины и любого ребра равно m. Поэтому, запустив на G алгоритм MAX TRIANGLE, решение MAX 2-SAT можно получить за время <math>O(f(m) \cdot g(3 \cdot 2^{n/3}))</math>, что соответствует <math>O(f(m) \cdot g(2^{n/3}))</math> в силу полиномиальности g. Этим завершается доказательство леммы 1. □ | Заметим, что количество вершин в G равно <math>3 \cdot 2^{n/3}</math>, а абсолютное значение веса любой вершины и любого ребра равно m. Поэтому, запустив на G алгоритм MAX TRIANGLE, решение MAX 2-SAT можно получить за время <math>O(f(m) \cdot g(3 \cdot 2^{n/3}))</math>, что соответствует <math>O(f(m) \cdot g(2^{n/3}))</math> в силу полиномиальности g. Этим завершается доказательство леммы 1. □ | ||
описывается процедура нахождения максимального треугольника быстрее, чем с помощью простого перебора, с использованием быстрого умножения матриц. Алон, Галил и Маргалит [1] (вслед за Ювалем [20]) показали, что произведение расстояний для матриц с элементами из <math>\Z [-W, W]</math> может быть вычислено с помощью быстрого умножения матриц в качестве подпрограммы. | Далее описывается процедура нахождения максимального треугольника быстрее, чем с помощью простого перебора, с использованием быстрого умножения матриц. Алон, Галил и Маргалит [1] (вслед за Ювалем [20]) показали, что произведение расстояний для матриц с элементами из <math>\Z [-W, W]</math> может быть вычислено с помощью быстрого умножения матриц в качестве подпрограммы. | ||
| Строка 110: | Строка 110: | ||
== Применение == | == Применение == | ||
Модифицировав конструкцию графа, можно решать другие задачи за время O(1 | Модифицировав конструкцию графа, можно решать другие задачи за время <math>O(1,732^n)</math>, такие как MAX CUT (максимальный разрез), MINIMUM BISECTION (минимальная бисекция) и SPARSEST CUT (самое неплотное сечение). В целом, любая задача оптимизации с ограничениями, в которой каждое ограничение имеет не более двух переменных, может быть решена быстрее с помощью описанного выше подхода. Более подробную информацию можно найти в работе [17] и в недавнем обзоре Вёгингера [19]. Схожая с вышеприведенным алгоритмом техника была также использована Дорном [6] с целью ускорения динамического программирования для некоторых задач на планарных графах (и вообще на графах с ограниченной путевой шириной). | ||
== Открытые вопросы == | == Открытые вопросы == | ||
• Необходимо улучшить использование памяти описанным выше алгоритмом. В настоящее время он требует | • Необходимо улучшить использование памяти описанным выше алгоритмом. В настоящее время он требует <math>\Theta(2^{2n/3})</math>. Очень интересен пока нерешенный вопрос: существует ли алгоритм для MAX 2-SAT со временем <math>O(1,99^n)</math>, использующий только полиномиальный объем памяти. На этот вопрос можно было бы ответить положительно, если бы удалось найти алгоритм решения задачи о k-кликах (k-CLIQUE) с полилогарифмическими затратами памяти и временем <math>n^{k \ \delta}</math> для некоторых <math>\delta > 0</math> и <math>k \ge 3</math>. | ||
• Хотелось бы найти алгоритм для MAX 2-SAT, работающий быстрее 2n и не требующий быстрого умножения матриц. Алгоритмы быстрого умножения матриц имеют печальную репутацию непрактичных. | • Хотелось бы найти алгоритм для MAX 2-SAT, работающий быстрее 2n и не требующий быстрого умножения матриц. Алгоритмы быстрого умножения матриц имеют печальную репутацию непрактичных. | ||
