Достаточное условие полиномиальной разрешимости случайных 3-КНФ формул

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Настоящая работа посвящена локализации случайных 3-КНФ формул, полиномиально разрешимых резолюционным алгоритмом. Показано, что случайные формулы с числом дизъюнктов, пропорциональным квадрату числа переменных, с вероятностью близкой к единице полиномиально разрешимы при коэффициенте пропорциональности, превышающем найденный порог.

Об авторах

С. И. Уваров

Институт проблем управления Российской академии наук

Автор, ответственный за переписку.
Email: suvarov@ipu.ru
Россия, Москва

Список литературы

  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
Скачать

© Российская академия наук, 2024