Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT

DOI10.1007/s10472-005-0426-4zbMath1100.68576arXivcond-mat/0206242OpenAlexW3005320095MaRDI QIDQ1777400

Simona Cocco, Remi Monasson

Publication date: 13 May 2005

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cond-mat/0206242

zbMATH Keywords

large deviationssatisfiabilityrestartDPLL

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (1)

On the entropy of protein families

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• The hardest constraint problems: A double phase transition
• Easy problems are sometimes hard
• Critical behavior in the computational cost of satisfiability testing
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Many hard examples for resolution
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• Sharp thresholds of graph properties, and the $k$-sat problem
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• A sharp threshold in proof complexity
• Determining computational complexity from characteristic ‘phase transitions’
• A machine program for theorem-proving
• Statistical mechanics methods and phase transitions in optimization problems
• Rigorous results for random (\(2+p)\)-SAT
• Results related to threshold phenomena research in satisfiability: Lower bounds
• Lower bounds for random 3-SAT via differential equations
• Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs

This page was built for publication: Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT