Sufficient condition for polynomial solvability of random 3-CNF formulas

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

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