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
From MaRDI portal
Publication:1777400
DOI10.1007/s10472-005-0426-4zbMath1100.68576arXivcond-mat/0206242MaRDI QIDQ1777400
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
68Q25: Analysis of algorithms and problem complexity
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
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
