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

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

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

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

С другой стороны, для фиксированных и малых значений k (особенно для k = 3) нижние границы r*~ обычно вычисляются алгоритмическими методами. Точнее, конструируется алгоритм, который для как можно большего rk выдает выполнимое истинностное присваивание для асимптотически почти всех формул фПг[Гк "у. Такой rk, очевидно, является нижней границей r*~. Чем проще алгоритм, тем легче провести вероятностный анализ возврата выполнимого истинностного присваивания для заданного гь, но тем меньше rk, для которого почти всегда асимптотически выдается выполнимое истинностное присваивание. В этом контексте были тщательно проанализированы алгоритмы DPLL без возвратов [4, 5] все большей сложности (см. обзоры [2, 9]). На каждом шаге такого алгоритма литералу задается значение TRUE, а затем получается сокращенная формула путем (1) удаления дизъюнктов, в которых встречается этот литерал, и (2) удаления отрицания этого литерала из дизъюнктов, в которых он встречается. На тех шагах, где существуют 1-дизъюнкты (так называемые вынужденные шаги), выбор литерала, который должен получить значение TRUE, осуществляется таким образом, чтобы 1-дизъюнкт стал выполнимым. На остальных шагах (называемых свободными) выбор литерала, который должен получить значение TRUE, осуществляется в соответствии с эвристикой, определяемой конкретным алгоритмом DPLL. За свободным шагом следует раунд последовательных вынужденных шагов. Для упрощения вероятностного анализа алгоритмов DPLL предполагается отсутствие у них возвратов: если алгоритм натыкается на противоречие, т. е. генерируется 0-дизъюнкт, он останавливает выполнение и сообщает о сбое, в противном случае он выдает выполнимое истинностное присваивание. Лучшая нижняя граница для порога выполнимости, полученная в результате такого анализа, составила 3,26 < r* (Ахлиоптас и Соркин [1]).

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

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

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

Во втором варианте на каждом свободном шаге 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-КНФ-алгоритмы на базе поиска с возвратом]]