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