Пороги для задачи выполнимости случайной k-КНФ

Ключевые слова и синонимы

Фазовые переходы (Phase transitions); вероятностный анализ эвристики Дэвиса-Путнам (Probabilistic analysis of a Davis-Putnam heuristic)

Постановка задачи

Рассмотрим n булевых переменных [math]\displaystyle{ V = \{ x_1, ..., x_n \} }[/math] и соответствующий набор из [math]\displaystyle{ 2n }[/math] литералов [math]\displaystyle{ L = \{х_1, \bar{х}_1, ..., x_n, \bar{x}_n \} }[/math]. k-дизъюнктом называется дизъюнкция [math]\displaystyle{ k }[/math] литералов, в которую каждая переменная входит не более одного раза. Случайная формула [math]\displaystyle{ \phi_{n, m} }[/math] в k-конъюнктивной нормальной форме (k-КНФ) представляет собой конъюнкцию [math]\displaystyle{ m }[/math] дизъюнктов, каждый из которых выбирается равномерно случайным и независимым образом среди [math]\displaystyle{ 2^k \tbinom{n}{k} }[/math] возможных k-дизъюнктов на n переменных в V. Плотностью [math]\displaystyle{ r_k }[/math] k-КНФ-формулы [math]\displaystyle{ \phi_{n, m} }[/math] называется отношение числа дизъюнктов к числу переменных m/n.

Было высказано предположение, что для каждого [math]\displaystyle{ k \ge 2 }[/math] существует критическая плотность [math]\displaystyle{ r^*_k }[/math], такая, что асимптотически почти все k-КНФ-формулы с плотностью [math]\displaystyle{ r \lt r^*_k \; (r \gt r^*_k) }[/math] являются выполнимыми (соответственно, невыполнимыми). До момента написания данной статьи гипотеза была доказана только для [math]\displaystyle{ k = 2 }[/math] [3, 11]. Для [math]\displaystyle{ k \ge 3 }[/math] гипотеза остается открытой, но подтверждается экспериментальными данными [14], а также теоретическими, но нестрогими работами, основанными на статистической механике [15]. Значение предполагаемого порога [math]\displaystyle{ r^*_3 }[/math] оценивается примерно в 4,27. Также были вычислены приблизительные значения предполагаемого порога для больших значений k.

Что касается строгих результатов, то Фридгут [10] доказал, что для каждого [math]\displaystyle{ k \ge 3 }[/math] существует последовательность [math]\displaystyle{ r^*_k(n) }[/math], такая, что для любого [math]\displaystyle{ \epsilon \gt 0 }[/math] асимптотически почти все k-КНФ формулы [math]\displaystyle{ \phi_n, _{\lfloor (r^*_k(n) - \epsilon )n\rfloor} (\phi_n, _{\lceil (r^*_k(n) + \epsilon )n \rceil} ) }[/math] являются выполнимыми (соответственно, невыполнимыми). Вопрос о сходимости последовательности [math]\displaystyle{ r^*_k(n), n = 0, 1, ... }[/math] для [math]\displaystyle{ k \ge 3 }[/math] остается открытым. Теперь положим

[math]\displaystyle{ r^{* -}_k = \underline{lim}_{n \to \infty} r^*_k(n) = sup \{ r_k: Pr [ \phi_{n, \lfloor r_k n \rfloor} }[/math] выполнимо [math]\displaystyle{ \to 1 ] \} }[/math]

и

[math]\displaystyle{ r^{* +}_k = \overline{lim}_{n \to \infty} r^*_k(n) = inf \{ r_k: Pr [ \phi_{n, \lceil r_k n \rceil} }[/math] выполнимо [math]\displaystyle{ \to 0 ] \} }[/math].

Очевидно, что [math]\displaystyle{ r^{* -}_k \le r^{* -}_k }[/math]. Ограничение снизу (сверху) [math]\displaystyle{ r^{* -}_k }[/math] ([math]\displaystyle{ r^{* +}_k }[/math], соответственно) с как можно большей (как можно меньшей, соответственно) границей стало предметом интенсивных исследований в последнее десятилетие.

Верхние границы [math]\displaystyle{ r^{* +}_k }[/math] вычисляются путем подсчета аргументов. Если точнее, стандартная техника заключается в вычислении ожидаемого количества выполнимых истинностных присваиваний случайной формулы с плотностью [math]\displaystyle{ r_k }[/math] и нахождении как можно меньшего значения [math]\displaystyle{ r_k }[/math], для которого это ожидаемое значение приближается к нулю. Тогда из неравенства Маркова следует, что при таком значении [math]\displaystyle{ r_k }[/math] случайная формула [math]\displaystyle{ \phi_n, _{\lceil (r_k n \rceil} }[/math] почти всегда асимптотически невыполнима. Это утверждение было уточнено в двух направлениях.

Во-первых, рассматриваются не все выполнимые истинностные присваивания, а их подкласс, обладающий следующим свойством: выполнимая формула всегда имеет выполнимое истинностное присваивание в рассматриваемом подклассе. В силу ограничения на рациональный выбор такого подкласса ожидаемое значение количества выполнимых истинностных присваиваний приближается к вероятности выполнимости и, таким образом, приводит к получению лучшей (меньшей) верхней границы [math]\displaystyle{ r_k }[/math]. Однако важно, чтобы подкласс был таким, чтобы ожидаемое значение количества выполнимых истинностных присваиваний можно было вычислить с помощью доступных вероятностных техник.

Во-вторых, при вычислении ожидаемого количества выполнимых истинностных присваиваний следует использовать типичные характеристики случайной формулы, то есть характеристики, общие для асимптотически почти всех формул. Опять же, это часто приводит к тому, что ожидаемое количество выполнимых истинностных присваиваний оказывается ближе к вероятности выполнимости (нетипичные формулы могут способствовать увеличению ожидаемого количества). Значительно более хорошие верхние границы для [math]\displaystyle{ r_3^{* +} }[/math] были вычислены путем подсчета аргументов, как указано выше (см. обзоры [6, 13]). Дюбуа, Буфхад и Мандлер [7] доказали, что [math]\displaystyle{ r_3^{*+} \lt 4.506 }[/math]. Это лучшая верхняя граница на момент написания статьи.

С другой стороны, для фиксированных и малых значений k (особенно для k = 3) нижние границы [math]\displaystyle{ r^{* -}_k }[/math] обычно вычисляются алгоритмическими методами. Точнее, конструируется алгоритм, который для как можно большего [math]\displaystyle{ r_k }[/math] выдает выполнимое истинностное присваивание для асимптотически почти всех формул [math]\displaystyle{ \phi_n, _{\lfloor (r_k n \rfloor} }[/math]. Такой [math]\displaystyle{ r_k }[/math], очевидно, является нижней границей [math]\displaystyle{ r_k^{*-} }[/math]. Чем проще алгоритм, тем легче провести вероятностный анализ возврата выполнимого истинностного присваивания для заданного [math]\displaystyle{ r_k }[/math], но тем меньше [math]\displaystyle{ r_k }[/math], для которого почти всегда асимптотически выдается выполнимое истинностное присваивание. В этом контексте были тщательно проанализированы алгоритмы DPLL без возвратов [4, 5] все большей сложности (см. обзоры [2, 9]). На каждом шаге такого алгоритма литералу задается значение TRUE, а затем получается приведенная формула путем (1) удаления дизъюнктов, в которых встречается этот литерал, и (2) удаления отрицания этого литерала из дизъюнктов, в которых он встречается. На тех шагах, где существуют 1-дизъюнкты (так называемые вынужденные шаги), выбор литерала, который должен получить значение TRUE, осуществляется таким образом, чтобы 1-дизъюнкт стал выполнимым. На остальных шагах (называемых свободными) выбор литерала, который должен получить значение TRUE, осуществляется в соответствии с эвристикой, определяемой конкретным алгоритмом DPLL. За свободным шагом следует раунд последовательных вынужденных шагов. Для упрощения вероятностного анализа алгоритмов DPLL предполагается отсутствие у них возвратов: если алгоритм натыкается на противоречие, т. е. генерируется 0-дизъюнкт, он останавливает выполнение и сообщает о сбое, в противном случае он выдает выполнимое истинностное присваивание. Лучшая нижняя граница для порога выполнимости, полученная в результате такого анализа, составила [math]\displaystyle{ 3.26 \lt r_3^{*-} }[/math] (Ахлиоптас и Соркин [1]).

Проанализированные ранее подобные алгоритмы (за исключением алгоритма Pure Literal [ ]) на свободном шаге учитывают только размер дизъюнкта, в котором встречается выбранный литерал. Благодаря этой ограниченности информации, используемой при выборе получающего значение литерала, редуцированная формула на каждом шаге остается случайной, обусловленной только текущим количеством 3- и 2-дизъюнкт и количеством переменных, еще не получивших присваивание. Такое сохранение «сильной» случайности позволяет провести успешный вероятностный анализ алгоритма достаточно несложным способом. Однако для k = 3 удается показать выполнимость только для плотностей до числа, слегка превышающего 3,26. В частности, в [ ] было показано, что это оптимальное значение, которое может быть достигнуто подобными алгоритмами.

Основные результаты

В работе [12] был описан (и затем проанализирован с вероятностной точки зрения) алгоритм DPLL, в котором на каждом свободном шаге выбирается литерал, которому должно быть задано значение TRUE, с учетом его степени (т. е. количества вхождений) в текущей формуле.

Алгоритм Greedy (глава 4.A в [12])

Первый вариант алгоритма очень прост: на каждом свободном шаге выбирается литерал с максимальным количеством вхождений, и ему задается значение TRUE. Заметим, что в этом жадном варианте литерал выбирается независимо от количества вхождений его отрицания. Этот алгоритм успешно выдает выполнимое истинностное присваивание для асимптотически почти всех формул с плотностью до числа, немного большего 3,42, устанавливая, что r*~ > 3,42. Его простота, контрастирующая с улучшением по сравнению с ранее полученными нижними границами, говорит о важности анализа эвристик, учитывающих информацию о степени текущей формулы.

Алгоритм CL (глава 5.A в [12])

Во втором варианте на каждом свободном шаге t также учитывается степень отрицания x литерала x, которому задано значение TRUE. В частности, литерал, которому задается значение TRUE, выбирается таким образом, чтобы по завершении раунда вынужденных шагов, следующих за свободным шагом t, предельное ожидаемое увеличение потока от 2-дизъюнктов до 1-дизъюнктов на единицу ожидаемого уменьшения потока от 3-дизъюнктов до 2-дизъюнктов было минимальным. Предельное значение математического ожидания, соответствующее каждому литералу, может быть вычислено из количества его положительных и отрицательных вхождений. Более конкретно, если mi ; i = 2, 3 равно ожидаемому потоку i-дизъюнктов в (i - 1)-дизъюнкты на каждом шаге раунда, а x – литерал, которому в начале раунда присвоено значение TRUE, то x выбирается таким образом, чтобы минимизировать отношение | ■^2j разностей 4 m2 и 4 m3 между началом и концом раунда. Следствием этого является ограничение скорости генерации 1-дизъюнктов наименьшим возможным числом на протяжении всего алгоритма. Для успешности вероятностного анализа нам нужно знать для каждого i,j количество литералов степени i, отрицание которых имеет степень j. Эта эвристика успешно выдает выполнимое истинностное присваивание для асимптотически почти всех формул с плотностью до числа, немного большего 3,52, устанавливая, что r*~ > 3,52.

Применение

SAT-решатели (программы для решения задачи выполнимости булевых формул) применяются, в частности, в таких областях, как верификация последовательных цепей, искусственный интеллект, автоматическое вычисление и планирование, СБИС, САПР, проверка моделей и другие виды формальной верификации. Недавно автоматические методы проверки моделей на основе SAT начали использоваться для эффективного поиска атак на протоколы безопасности.

Открытые вопросы

Главной нерешенной проблемой в этой области является формальное доказательство существования порога r* для всех (или хотя бы некоторых) к > 3. Строгое вычисление верхних и нижних границ, лучших, чем упомянутые выше, также вызывает определенный интерес. Связанные с этим результаты и проблемы возникают в рамках вариантов задачи выполнимости, а также проблемы раскрашиваемости.

См. также

• k-КНФ-алгоритмы на базе поиска с возвратом
• Алгоритмы локального поиска для k-КНФ
• Максимальная выполнимость формул в 2-КНФ
• Границы хвостов для задач о размещении

Литература

1. Achioptas, D., Sorkin,G.B.: Optimal myopic algorithms for random 3-sat. In: 41st Annual Symposium on Foundations of Computer Science, pp. 590-600. IEEE Computer Society, Washington (2000)

2. Achlioptas, D.: Lower bounds for random 3-sat via differential equations. Theor. Comput. Sci. 265(1-2), 159-185 (2001)

3. Chvatal,V., Reed, B.: Mick gets some (the odds are on his side). In: 33rd Annual Symposium on Foundations of Computer Science, pp. 620-627. IEEE Computer Society, Pittsburgh (1992)

4. Davis, M., Logemann, G., Loveland, D.: A machine program for theorem-proving. Commun. ACM 5, 394-397 (1962)

5. Davis, M., Putnam, H.: A computing procedure for quantification theory. J. Assoc. Comput. Mach. 7(4), 201 -215 (1960)

6. Dubois, O.: Upper bounds on the satisfiability threshold. Theor. Comput. Sci. 265,187-197 (2001)

7. Dubois, O., Boufkhad, Y., Mandler, J.: Typical random 3-sat formulae and the satisfiability threshold. In: 11 th ACM-SIAM symposium on Discrete algorithms, pp. 126-127. Society for Industrial and Applied Mathematics, San Francisco (2000)

8. Franco, J.: Probabilistic analysis of the pure literal heuristic for the satisfiability problem. Annal. Oper. Res. 1, 273-289 (1984)

9. Franco, J.: Results related to threshold phenomena research in satisfiability: Lower bounds. Theor. Comput. Sci. 265,147-157 (2001)

10. Friedgut, E.: Sharp thresholds of graph properties, and the k-sat problem. J. AMS 12,1017-1054 (1997)

11. Goerdt, A.: A threshold for unsatisfiability. J. Comput. Syst. Sci. 33,469^86(1996)

12. Kaporis, A.C., Kirousis, L.M., Lalas, E.G.: The probabilistic analysis of a greedy satisfiability algorithm. Random Struct. Algorithms 28(4), 444-480 (2006)

13. Kirousis, L., Stamatiou, Y., Zito, M.: The unsatisfiability threshold conjecture: the techniques behind upper bound improvements. In: A. Percus, G. Istrate, С Moore (eds.) Computational Complexity and Statistical Physics, Santa Fe Institute Studies in the Sciences of Complexity, pp. 159-178. Oxford University Press, New York (2006)

14. Mitchell, D., Selman, B., Levesque, H.: Hard and easy distribution of sat problems. In: 10th National Conference on Artificial Intelligence, pp. 459^65. AAAI Press, Menlo Park (1992)

15. Monasson, R., Zecchina, R.: Statistical mechanics of the random k-sat problem. Phys. Rev. E 56,1357-1361 (1997)