4652
правки
Пороги для задачи выполнимости случайной k-КНФ: различия между версиями
Перейти к навигации
Перейти к поиску
Пороги для задачи выполнимости случайной k-КНФ (посмотреть исходный код)
Версия от 13:16, 13 марта 2025
, 13 март→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 18: | Строка 18: | ||
Очевидно, что r* | Очевидно, что <math>r^{* -}_k \le r^{* -}_k</math>. Ограничение снизу (сверху) <math>r^{* -}_k</math> (<math>r^{* +}_k</math>, соответственно) с как можно большей (как можно меньшей, соответственно) границей стало предметом интенсивных исследований в последнее десятилетие. | ||
Верхние границы <math>r^{* +}_k</math> вычисляются путем подсчета аргументов. Если точнее, стандартная техника заключается в вычислении ожидаемого количества выполнимых истинностных присваиваний случайной формулы с плотностью <math>r_k</math> и нахождении как можно меньшего значения <math>r_k</math>, для которого это ожидаемое значение приближается к нулю. Тогда из неравенства Маркова следует, что при таком значении <math>r_k</math> случайная формула <math>\phi_n, _{\lceil (r_k n \rceil}</math> почти всегда асимптотически невыполнима. Это утверждение было уточнено в двух направлениях. | |||
Во-первых, рассматриваются не все выполнимые истинностные присваивания, а их подкласс, обладающий следующим свойством: выполнимая формула всегда имеет выполнимое истинностное присваивание в рассматриваемом подклассе. В силу ограничения на рациональный выбор такого подкласса ожидаемое значение количества выполнимых истинностных присваиваний приближается к вероятности выполнимости и, таким образом, приводит к получению лучшей (меньшей) верхней границы <math>r_k</math>. Однако важно, чтобы подкласс был таким, чтобы ожидаемое значение количества выполнимых истинностных присваиваний можно было вычислить с помощью доступных вероятностных техник. | |||
Во-вторых, при вычислении ожидаемого количества выполнимых истинностных присваиваний следует использовать ''типичные'' характеристики случайной формулы, то есть характеристики, общие для асимптотически почти всех формул. Опять же, это часто приводит к тому, что ожидаемое количество выполнимых истинностных присваиваний оказывается ближе к вероятности выполнимости (нетипичные формулы могут способствовать увеличению ожидаемого количества). Значительно более хорошие верхние границы для <math>r_3^{* +}</math> были вычислены путем подсчета аргументов, как указано выше (см. обзоры [6, 13]). Дюбуа, Буфхад и Мандлер [7] доказали, что <math>r_3^{*+} < 4.506</math>. Это лучшая верхняя граница на момент написания статьи. | |||
Во-вторых, при вычислении ожидаемого количества выполнимых истинностных присваиваний следует использовать типичные характеристики случайной формулы, то есть характеристики, общие для асимптотически почти всех формул. Опять же, это часто приводит к тому, что ожидаемое количество выполнимых истинностных присваиваний оказывается ближе к вероятности выполнимости (нетипичные формулы могут способствовать увеличению ожидаемого количества). Значительно более хорошие верхние границы для | |||