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

共 12 条

[1] Alekhnovich Michael, 2003, Proceedings of the Steklov Institute of Mathematics, V242, P18
[2] Towards understanding and harnessing the potential of clause learning
Beame, P
Kautz, H
Sabharwal, A
[J]. JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2004, 22 : 319 - 351
[3] Biere A., 2021, Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, V336, DOI DOI 10.3233/FAIA336
[4] BRODER AZ, 1993, PROCEEDINGS OF THE FOURTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P322
[5] The importance of the P versus NP question
Cook, S
[J]. JOURNAL OF THE ACM, 2003, 50 (01) : 27 - 29
[6] Ganesh Vijay, 2020, On the unreasonable effectiveness of SAT solvers
[7] Gomes CP, 2008, FOUND ARTIF INTELL, P89, DOI 10.1016/S1574-6526(07)03002-7
[8] THE INTRACTABILITY OF RESOLUTION
HAKEN, A
[J]. THEORETICAL COMPUTER SCIENCE, 1985, 39 (2-3) : 297 - 308
[9] The probabilistic analysis of a greedy satisfiability algorithm
Kaporis, Alexis C.
Kirousis, Lefteris M.
Lalas, Efthimios G.
[J]. RANDOM STRUCTURES & ALGORITHMS, 2006, 28 (04) : 444 - 480
[10] CRITICAL-BEHAVIOR IN THE SATISFIABILITY OF RANDOM BOOLEAN EXPRESSIONS
KIRKPATRICK, S
SELMAN, B
[J]. SCIENCE, 1994, 264 (5163) : 1297 - 1301

← 1 2 →