- Код статьи
- 10.31857/S2686954324040067-1
- DOI
- 10.31857/S2686954324040067
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том 518 / Номер выпуска 1
- Страницы
- 35-39
- Аннотация
- Настоящая работа посвящена локализации случайных 3-КНФ формул, полиномиально разрешимых резолюционным алгоритмом. Показано, что случайные формулы с числом дизъюнктов, пропорциональным квадрату числа переменных, с вероятностью близкой к единице полиномиально разрешимы при коэффициенте пропорциональности, превышающем найденный порог.
- Ключевые слова
- 3-КНФ дизъюнкт резолюция алгоритмическая сложность задача выполнимости
- Дата публикации
- 15.06.2024
- Год выхода
- 2024
- Всего подписок
- 0
- Всего просмотров
- 34
Библиография
- 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.
