4632
правки
Пороги для задачи выполнимости случайной k-КНФ: различия между версиями
Материал из WEGA
Пороги для задачи выполнимости случайной k-КНФ (посмотреть исходный код)
Версия от 05:54, 5 марта 2025
, 5 март→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 10: | Строка 10: | ||
Что касается строгих результатов, то Фридгут [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> остается открытым. Теперь положим | Что касается строгих результатов, то Фридгут [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 = \underline{lim}_{n \to \infty} r^*_k(n) = sup \{ r_k: Pr [ \phi_{n, \lfloor r_k n \rfloor} </math> выполнимо <math>\to 1 ] \}</math> | |||
и | |||
<math>r^{* +}_k = \overline{lim}_{n \to \infty} r^*_k(n) = inf \{ r_k: Pr [ \phi_{n, \lceil r_k n \rceil} </math> выполнимо <math>\to 0 ] \}</math>. | |||
