Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances

DOI10.1016/j.tcs.2004.02.034zbMath1068.68067OpenAlexW2142281466MaRDI QIDQ596103

Simona Cocco, Remi Monasson

Publication date: 10 August 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.02.034

zbMATH Keywords

SatisfiabilityAnalysis of algorithmsBacktrack

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorial probability (60C05)

Related Items

An efficient approach to solving random \(k\)-SAT problems

Cites Work

• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• Easy problems are sometimes hard
• Differential equations for random processes and random graphs
• Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
• 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
• A machine program for theorem-proving
• The dynamics of proving uncolourability of large random graphs: I. Symmetric colouring heuristic
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item