78917

Автор(ы): 

Уваров С. И. (ИПУ РАН, Лаборатория 27)

Автор(ов): 

1

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

Достаточное условие полиномиальной разрешимости случайных 3-КНФ формул

ISBN/ISSN: 

ISSN: 2686-9543

DOI: 

10.31857/S2686954324040067

Наименование источника: 

  • Доклады Российской академии наук. Математика, информатика, процессы управления

Обозначение и номер тома: 

Т: 518. № 1

Город: 

  • Москва

Издательство: 

  • РАН

Год издания: 

2024

Страницы: 

35-39
Аннотация
Настоящая работа посвящена локализации случайных 3-КНФ формул, полиномиально разрешимых резолюционным алгоритмом. Показано, что случайные формулы с числом дизъюнктов, пропорцио- нальным квадрату числа переменных, с вероятностью близкой к единице полиномиально разрешимы при коэффициенте пропорциональности, превышающем найденный порог.

Библиографическая ссылка: 

Уваров С.И. Достаточное условие полиномиальной разрешимости случайных 3-КНФ формул // Доклады Российской академии наук. Математика, информатика, процессы управления. 2024. Т: 518. № 1 . С. 35-39 .

Публикация имеет версию на другом языке или вышла в другом издании, например, в электронной (или онлайн) версии журнала: 

Да

Связь с публикацией: 

Уваров С.И. Empirical evaluation of the asymptotic behavior of the analysis complexity of hard random 3-cnf formulas. // Machine Learning and Artificial Intelligence. 2022. Vol. 360. С. 28-34.