Sufficient condition for polynomial solvability of random 3-CNF formulas

Мұқаба

Дәйексөз келтіру

Толық мәтін

Ашық рұқсат Ашық рұқсат
Рұқсат жабық Рұқсат берілді
Рұқсат жабық Тек жазылушылар үшін

Аннотация

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.

Негізгі сөздер

Авторлар туралы

S. Uvarov

V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences

Хат алмасуға жауапты Автор.
Email: suvarov@ipu.ru
Ресей, Moscow

Әдебиет тізімі

  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.

Қосымша файлдар

Қосымша файлдар
Әрекет
1. JATS XML
Жүктеу

© Russian Academy of Sciences, 2024