Автор(ы): Уваров С. И. (ИПУ РАН, Лаборатория 27)Автор(ов): 1 Параметры публикацииТип публикации: Статья в журнале/сборникеНазвание: Sufficient Condition for Polynomial Solvability of Random 3-CNF Formulas.ISBN/ISSN: ISSN 1064-5624DOI: 10.1134/S1064562424601148Наименование источника: Doklady MathematicsОбозначение и номер тома: Vol. 110, № 1Город: MoscowИздательство: Pleiades Publishing, Ltd.Год издания: 2024Страницы: 323-327 АннотацияThis paper is devoted to the localisation of random 3-CNF formulas that are polynomially solvable by the resolution algorithm. It is shown that random formulas with the number of clauses proportional to the square of the number of variables, are polynomially solvable with probability close to unity when the proportionality coefficient exceeds the found threshold. Библиографическая ссылка: Уваров С.И. Sufficient Condition for Polynomial Solvability of Random 3-CNF Formulas. / Doklady Mathematics. Moscow: Pleiades Publishing, Ltd., 2024. Vol. 110, № 1. С. 323-327 .