4622
правки
Пороги для задачи выполнимости случайной k-КНФ: различия между версиями
Материал из WEGA
Пороги для задачи выполнимости случайной k-КНФ (посмотреть исходный код)
Версия от 04:54, 5 марта 2025
, 5 март→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Было высказано предположение, что для каждого <math>k \ge 2</math> существует критическая плотность <math>r^*_k</math>, такая, что асимптотически почти все k-КНФ формулы с плотностью r < r* (r > | Было высказано предположение, что для каждого <math>k \ge 2</math> существует критическая плотность <math>r^*_k</math>, такая, что асимптотически почти все k-КНФ-формулы с плотностью <math>r < r^*_k \; (r > r^*_k)</math> являются выполнимыми (соответственно, невыполнимыми). До момента написания данной статьи гипотеза была доказана только для <math>k = 2</math> [3, 11]. Для <math>k \ge 3</math> гипотеза остается открытой, но подтверждается экспериментальными данными [14], а также теоретическими, но нестрогими работами, основанными на статистической механике [15]. Значение предполагаемого порога <math>r^*_3</math> оценивается примерно в 4,27. Также были вычислены приблизительные значения предполагаемого порога для больших значений k. | ||
Что касается строгих результатов, то Фридгут [10] доказал, что для каждого k > | Что касается строгих результатов, то Фридгут [10] доказал, что для каждого <math>k \ge 3</math> существует последовательность <math>r^*_k(n)</math>, такая, что для любого <math>\epsilon > 0</math> асимптотически почти все k-КНФ формулы Фп,1(г*к(п)-€)п\ (Фп,\(г*кМ+€)п-\) являются выполнимыми (соответственно, невыполнимыми). Вопрос о сходимости последовательности r*(n), n = 0; 1; для k > 3 остается открытым. Теперь положим | ||
