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

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

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

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