- PII
- 10.31857/S2686954324040067-1
- DOI
- 10.31857/S2686954324040067
- Publication type
- Article
- Status
- Published
- Authors
- Volume/ Edition
- Volume 518 / Issue number 1
- Pages
- 35-39
- Abstract
- 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.
- Keywords
- 3-КНФ дизъюнкт резолюция алгоритмическая сложность задача выполнимости
- Date of publication
- 15.06.2024
- Year of publication
- 2024
- Number of purchasers
- 0
- Views
- 35
References
- 1. Cook S. The Importance of the P versus NP Question // JACM. 2003. V. 50. P. 27–29.
- 2. Biere A., Heule M., Maaren H., Walsh T. Handbook of Satisfiability (Second Edition). IOS Press, 2021. https://doi.org/10.3233/FAIA336
- 3. Gomes C., Rautz H., Sabharwal A., Selman B. Satisfiability Solvers // Handbook of Knowledge Representation. 2008. P. 89–133.
- 4. Beame P., Kautz H.A., Sabharwal A. Towards Understanding and Harnessing the Potential of Clause Learning // Journal of Artificial Intelligence Research. 2004. V. 22. P. 319–351.
- 5. Ganesh V., Vardi M. On the Unreasonable Effectiveness of SAT Solvers // Beyond the Worst-Case Analysis of Algorithms. 2020. P. 547–566.
- 6. Kirkpatrick S., Selman B. Critical Behavior in the Satisfiability of Random Boolean Expressions // Science. 1994. V. 264. № 5163. P. 1297–1301.
- 7. Merzard M., Parisi G., Zecchina R. Analitic and Algorithmic Solution of Random Satisfiability Problems // Science. 2002. V. 297. P. 812–815.
- 8. Kaporis A.C., Kirousis L.M., Laias E.G. The Probabilistic Analysis of a Greedy Satisfiability Algorithm // Random Structures and Algorithms. 2006. V. 28. № 4. P. 444–480.
- 9. Broder A.Z., Frieze A.M., Upfal E. On the Satisfiability and Maximum Satisfiability of Random 3-CNF Formulas // In 4th ACMSIAM Symposium on Discrete Algorithms. SIAM. 1993. P. 322–330.
- 10. Mitzenmacher M. Tight Thresholds for the Pure Literal Rule // DEC/SRC Technical Note 1997–011. 1997.
- 11. Haken A. The Intractability of Resolution // Theoretical Computer Science. 1985. V. 39. P. 297–308.
- 12. Алехнович М.В., Разборов А.А. Нижние оценки для полиномиального исчисления в случае идеалов, отличных от биномиальных // Труды математического института им. В.А. Стеклова. 2003. Т. 242. С. 23–43.
