Sufficient Condition for Polynomial Solvability of Random 3-CNF Formulas

被引：0

作者：

Uvarov, S., I ^{[1
]}

机构：

[1] Russian Acad Sci, V A Trapeznikov Inst Control Sci, Moscow, Russia

来源：

DOKLADY MATHEMATICS | 2024年 / 110卷 / 01期

关键词：

3-CNF; clause; resolution; complexity; satisfiability problem; SATISFIABILITY;

D O I：

10.1134/S1064562424601148

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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.

引用

页码：323 / 327

页数：5