Автор(ы): Уваров С. И. (ИПУ РАН, Лаборатория 27)Автор(ов): 1 Параметры публикацииТип публикации: Статья в журнале/сборникеНазвание: Достаточное условие полиномиальной разрешимости случайных 3-КНФ формулISBN/ISSN: ISSN: 2686-9543DOI: 10.31857/S2686954324040067Наименование источника: Доклады Российской академии наук. Математика, информатика, процессы управленияОбозначение и номер тома: Т: 518. № 1 Город: МоскваИздательство: РАНГод издания: 2024Страницы: 35-39 АннотацияНастоящая работа посвящена локализации случайных 3-КНФ формул, полиномиально разрешимых резолюционным алгоритмом. Показано, что случайные формулы с числом дизъюнктов, пропорцио- нальным квадрату числа переменных, с вероятностью близкой к единице полиномиально разрешимы при коэффициенте пропорциональности, превышающем найденный порог. Библиографическая ссылка: Уваров С.И. Достаточное условие полиномиальной разрешимости случайных 3-КНФ формул // Доклады Российской академии наук. Математика, информатика, процессы управления. 2024. Т: 518. № 1 . С. 35-39 .
