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

Что касается строгих результатов, то Фридгут [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 \le r^{* -}_k</math>. Ограничение снизу (сверху) <math>r^{* -}_k</math> (<math>r^{* +}_k</math>, соответственно) с как можно большей (как можно меньшей, соответственно) границей стало предметом интенсивных исследований в последнее десятилетие.