4817
правок
Пороги для задачи выполнимости случайной k-КНФ: различия между версиями
Перейти к навигации
Перейти к поиску
Пороги для задачи выполнимости случайной k-КНФ (посмотреть исходный код)
Версия от 15:06, 4 марта 2025
, 4 март→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Фазовые переходы (''Phase transitions''); вероятностный анализ эвристики Дэвиса-Путнам (''Probabilistic analysis of a Davis-Putnam heuristic'') == Постановка задачи == Рассмотрим n булевых переменных V = fx1...xng и соответствующий набор из 2n литералов L = {х\,х\...xn;xng....») |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Рассмотрим n булевых переменных V = | Рассмотрим 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. | ||