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

Рассмотрим n булевых переменных <math>V = \{ x_1, ..., x_n \}</math> и соответствующий набор из <math>2n</math> литералов <math>L = \{х_1, \bar{х}_1, ..., x_n, \bar{x}_n \} </math>. k-дизъюнктом называется дизъюнкция <math>k</math> литералов, в которую каждая переменная входит не более одного раза. Случайная формула <math>\phi_{n, m}</math> в k-конъюнктивной нормальной форме (k-КНФ) представляет собой конъюнкцию <math>m</math> дизъюнктов, каждый из которых выбирается равномерно случайным и независимым образом среди <math>2^k \binom{n}{k}</math> возможных k-дизъюнктов на n переменных в V. Плотностью <math>r_k</math> k-КНФ-формулы <math>\phi_{n, m}</math> называется отношение числа дизъюнктов к числу переменных m/n.

Было высказано предположение, что для каждого k > 2 существует критическая плотность r* такая, что асимптотически почти все (а.а.а.) k-КНФ формулы с плотностью r < r* (r > г*) являются выполнимыми (соответственно, невыполнимыми). До момента написания данной статьи гипотеза была доказана только для k = 2 [3, 11]. Для k > 3 гипотеза остается открытой, но подтверждается экспериментальными данными [ ], а также теоретическими, но нестрогими работами, основанными на статистической механике [ ]. Значение предполагаемого порога r* оценивается примерно в 4,27. Также были вычислены приблизительные значения предполагаемого порога для больших значений k.