Новый алгоритм для задачи выполнения наибольшего количества дизъюнктов

Оглавление

Аннотация 3
Введение 5
1 Обзор литературы 10
1.1 Историяразвитияобласти . . . . . . . . . . . . . . . . . . 10
1.2 Правилаупрощения...................... 12
1.3 Выводы............................. 15
2 Уменьшенная мера 16
2.1 Мотивация........................... 16
2.2 Определение.......................... 16
2.3 Свойства ............................ 17
2.4 Выводы............................. 20
3 Разбор 5-переменных 22
3.1 Общиенаблюдения ...................... 22
3.2 Разбор(4,1)-переменных . . . . . . . . . . . . . . . . . . . 25
3.3 Разбор (3, 2)-переменных в двух дизъюнктах длины 1 . . 27
3.4 Разбор (3, 2)-литералов в дизъюнкте длины 1 . . . . . . . 30
3.5 Разбор других (3, 2)-переменных . . . . . . . . . . . . . . 32
3.6 Выводы............................. 41
4 Разбор 4-переменных 42
4.1 Общиенаблюдения ...................... 42
4.2 Разбор(2,2)-переменных . . . . . . . . . . . . . . . . . . . 43
4.3 Разбор (3, 1)-переменных – не одиночек . . . . . . . . . . 48
4.4 Разбор(3,1)-одиночек..................... 50
4.5 Выводы............................. 53
Заключение 54
Список литературы 57

Введение

Актуальность задачи

Задача о максимальной выполнимости, или, сокращённо, MAXSAT, как оптимизационная версия задачи о выполнимости (сокращённо SAT), одной из самых известных NP-полных задач, имеет широкий круг при-менений, от анализа данных [4] до медицины [12]. При этом не толь-ко задача MAXSAT, но многие её частные случаи, такие, как (n, 3)-MAXSAT, являются NP-трудными [15].

Гипотеза об экспоненциальном времени говорит, что задача 3SAT, то есть задача булевой выполнимости с дополнительным ограничени-ем, что длина каждого дизъюнкта не более трёх, не может быть реше-на быстрее, чем за экспоненциальное время от количества переменных. Можно показать, что из этого следует отсутствие субэкспоненциаль-ного алгоритма и относительно длины входа. Как следствие, задача о максимальной выполнимости также не может быть решена за субэкспо-ненциальное время от длины входа, так как наличие такого алгоритма автоматически влекло бы за собой существование такого алгоритма и для 3SAT.
...

1. Обзор литературы

1.1. История развития области

Задача булевой выполнимости была исторически первой задачей, для которой была доказана NP-полнота (этот известный факт называ-ется теоремой Кука-Левина). Задача о максимальной выполнимости, как оптимизационная версия этой задачи, автоматически является NP-полной и изучается с тех времён.

История развития точных алгоритмов для MAXSAT представлена в таблицах 1.1 – 1.4.
Таблица 1.1: Развитие алгоритмов для задачи MAXSAT

Работа
Год
Результат

Нидермайер и Россманит [14]
1999
O∗(1.1279L) = O∗(20.1737L)
–
Банзал и Раман [2]
1999
O∗(1.1057L) = O∗(20.1450L)
16.5%

Видно, что со времён работы [2] значимого улучшения не произо-шло. В решении задачи в других мерах, связанных с количеством дизъ-юнктов при этом, как показано чуть ниже, существовал прогресс.
...

Определение 2.1. Уменьшенной мерой формулы F называется вели-чина d = L − n3.

Поскольку n3 является неотрицательной величиной, для любой фор-мулы d ≤ L. Таким образом, любой алгоритм, работающий за O∗(αd),

16
автоматически работает за O∗(αL). Следовательно, достаточно суще-ствования алгоритма за O∗(αd). В дальнейшем в работе строится алго-ритм относительно именно уменьшенной меры.

Отметим, что такую меру можно записать в следующем виде:

∑ ∑
d = L − n3 = knk − n3 = 2n3 + knk (1)

k≥3 k≥4

Для задач (n, 4)-MAXSAT и (n, 5)-MAXSAT эта запись имеет вид d = 2n3 + 4n4 и d = 2n3 + 4n4 + 5n5, соответственно. В частности, для мотивации, представленной в разделе 2.1, видно, что при удалении од-ного литерала у 4-переменной эта мера уменьшается на 2, то есть на столько же, на сколько она уменьшается при удалении одного литерала

• 3-переменной.
...

3. Разбор 5-переменных

3.1. Общие наблюдения

Итак, после того, как правило расщепления 2.1 неприменимо, остал-ся экземпляр задачи (n, 5)-MAXSAT. В данном разделе представлен разбор случаев, в совокупности позволяющих избавиться от всех 5-переменных. Прежде всего, несколько наблюдений.

Во-первых, не умаляя общности, 5-переменная может быть (4, 1)-переменной или (3, 2)-переменной. В силу правила упрощения 1.5, в первом случае переменная может встречаться в дизъюнктах длины 1 лишь отрицательно, во втором случае – либо дважды отрицательно, ли-бо однажды положительно или отрицательно. Каждый из этих случаев разобран в разделах этой главы.

Во-вторых, вспомним доказательство леммы 2.1. В доказательстве изменение уменьшенной длины формулы считалось как сумма измене-ний весов всех переменных. Для 5-переменных оказывается, что случа-ев переменных-соседей немного. Все эти случаи приведены в таблице 3.1. В первом столбце перечислено количество вхождений во всю фор-мулу.
...

4. Разбор 4-переменных

4.1. Общие наблюдения

Прежде всего, без ограничения общности, как и в прошлой гла-ве, все 4-переменные являются либо (2, 2)-переменными, либо (3, 1)-переменными.

Мера d, как указано в мотивации в разделе 2.1, разрабатывалась под задачу (n, 4)-MAXSAT для сглаживания разницы в свойствах меж-ду 3-переменными и 4-переменными. Для этой задачи она, как уже ука-зывалось выше, имеет очень простой вид

d = 2n3 + 4n4

Прежде всего, очевидно, что это число всегда чётное. Это объяс-няет то, что в этой главе все векторы расщепления чётные.

Более того, очень часто будет достаточно следующей леммы.

Лемма 4.1. Пусть l – 4-литерал в формуле (n, 4)-MAXSAT вида

(l ∨ C1) ∧ · · · ∧ (l ∨ Ci) ∧ (l ∨ D1) ∧ · · · ∧ (l ∨ Dj) ∧ F ′

Пусть в объединении Ci встречаются литералы хотя бы k раз-личных переменных. Тогда при означивании l = 1 мера d уменьшается хотя бы на 4 + 2k.

Доказательство.
...

Заключение

Itaque earum rerum hic tene-

tur a sapiente delectus, ut aut

reiciendis voluptatibus maiores

alias consequatur aut perferen-

dis doloribus asperiores repellat.

M. Tullius Cicero

Основным результатом работы является следующая теорема. По сравнению с предыдущим лучшим результатом в области [2] она даёт улучшение в логарифмической шкале на 11.7%.

Теорема 5.1. Существует алгоритм для задачи MAXSAT, работаю-щий за O∗(1.0927L).

Доказательство. Как показано в разделе 2.1, любой алгоритм за O∗(αd) работает и за O∗(αL).

Алгоритм за O∗(1.0927d) представлен в главах 2 – 4. Он последова-тельно выполняет правила упрощения и расщепления до тех пор, пока формула не станет экземпляром задачи (n, 3)-MAXSAT, после чего за-пускается алгоритм, представленный в работе [3] для этой задачи.

Полученные оценки на вектора расщепления представлены для удоб-ства в таблице 5.1. Последняя строчка относится к работе [3].
...