Sufficient condition for polynomial solvability of random 3-CNF formulas

DOI10.1134/s1064562424601148MaRDI QIDQ6644123

S. I. Uvarov

Publication date: 27 November 2024

Published in: Doklady Mathematics (Search for Journal in Brave)

zbMATH Keywords

complexitysatisfiability problemresolutionclause3-CNF

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects of satisfiability (68R07)

Cites Work

• The intractability of resolution
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• The importance of the P versus NP question
• On the Unreasonable Effectiveness of SAT Solvers
• The probabilistic analysis of a greedy satisfiability algorithm
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Sufficient condition for polynomial solvability of random 3-CNF formulas