Statistical physics analysis of the backtrack resolution of random 3-SAT instances

MaRDI QIDQ2741512zbMATH OpenFDO

Authors Simona Cocco, R. Monasson

Publication date 24 September 2001

zbMATH Keywords

backtrack algorithmscomplexityrandom 3-SAT instancessearch tree

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances
• scientific article; zbMATH DE number 2159023
• 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
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• scientific article; zbMATH DE number 5004842

Cited in

(7)

• Random 3-SAT: The plot thickens
• Bose-Einstein condensation in satisfiability problems
• Satisfiability by Maxwell-Boltzmann and Bose-Einstein statistical distributions
• Complexity of coloring random graphs: an experimental study of the hardest region
• scientific article; zbMATH DE number 2159023 (Why is no real title available?)
• Principles and Practice of Constraint Programming – CP 2004
• Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances

This page was built for publication: Statistical physics analysis of the backtrack resolution of random 3-SAT instances

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2741512)