Аннотация:
Настоящая работа посвящена локализации случайных 3-КНФ формул, полиномиально разрешимых резолюционным алгоритмом. Показано, что случайные формулы с числом дизъюнктов, пропорциональным квадрату числа переменных, с вероятностью близкой к единице полиномиально разрешимы при коэффициенте пропорциональности, превышающем найденный порог.
Ключевые слова:
3-КНФ , дизъюнкт, резолюция, алгоритмическая сложность, задача выполнимости.
УДК:510
Статья представлена к публикации:С. Н. Васильев Поступило: 22.04.2024 После доработки: 11.06.2024 Принято к публикации: 16.07.2024
