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

Первый вариант алгоритма очень прост: на каждом свободном шаге выбирается литерал с максимальным количеством вхождений, и ему задается значение 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.