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

Что касается строгих результатов, то Фридгут [10] доказал, что для каждого k > 3 существует последовательность r*(n) такая, что для любого e > 0, а.а.а. k-КНФ формулы Фп,1(г*к(п)-€)п\ (Фп,\(г*кМ+€)п-\) являются выполнимыми (соответственно, невыполнимыми). Вопрос о сходимости последовательности r*(n), n = 0; 1;  для k > 3 остается открытым. Теперь положим

Во-вторых, при вычислении ожидаемого количества выполнимых истинностных присваиваний следует использовать типичные характеристики случайной формулы, то есть характеристики, общие для а.а.а. формул. Опять же, это часто приводит к тому, что ожидаемое количество выполнимых истинностных присваиваний оказывается ближе к вероятности выполнимости (нетипичные формулы могут способствовать увеличению ожидаемого количества). Значительно более хорошие верхние границы для r*+ были вычислены путем подсчета аргументов, как указано выше (см. обзоры [6, 13]). Дюбуа, Буфхад и Мандлер [ ] доказали, что r*+ < 4,506. Это лучшая верхняя граница на момент написания статьи.

С другой стороны, для фиксированных и малых значений 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]).