79340

Автор(ы): 

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

Автор(ов): 

1

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

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

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

Название: 

Sufficient Condition for Polynomial Solvability of Random 3-CNF Formulas.

ISBN/ISSN: 

ISSN 1064-5624

DOI: 

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 .

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

Да

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

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