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

DOI10.1016/J.TCS.2004.02.034MaRDI QIDQ596103zbMATH OpenOpenAlexFDO

Authors Simona Cocco, R. 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

Analysis of algorithmsBacktrackSatisfiability

Mathematics Subject Classification ID

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

Recommendations

• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• An average analysis of backtracking on random constraint satisfaction problems
• scientific article; zbMATH DE number 4080977
• Computer Science Logic
• Statistical physics analysis of the backtrack resolution of random 3-SAT instances
• Average case results for satisfiability algorithms under the random-clause-width model
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• scientific article; zbMATH DE number 1444322
• Average Performance of Heuristics for Satisfiability
• scientific article; zbMATH DE number 1445295

Cites work

• scientific article; zbMATH DE number 5004842 (Why is no real title available?)
• scientific article; zbMATH DE number 1113992 (Why is no real title available?)
• scientific article; zbMATH DE number 1947423 (Why is no real title available?)
• scientific article; zbMATH DE number 2080304 (Why is no real title available?)
• scientific article; zbMATH DE number 1369843 (Why is no real title available?)
• scientific article; zbMATH DE number 1445295 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• A machine program for theorem-proving
• A sharp threshold in proof complexity
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Differential equations for random processes and random graphs
• Easy problems are sometimes hard
• Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
• Lower bounds for random 3-SAT via differential equations
• Many hard examples for resolution
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• Results related to threshold phenomena research in satisfiability: Lower bounds
• Rigorous results for random (\(2+p)\)-SAT
• SAT2000. Highlights of satisfiability research in the year 2000. 3rd international workshop, September 1998
• Sharp thresholds of graph properties, and the $k$-sat problem
• Statistical mechanics methods and phase transitions in optimization problems
• The dynamics of proving uncolourability of large random graphs: I. Symmetric colouring heuristic

Cited in

(7)

• 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
• scientific article; zbMATH DE number 2080304 (Why is no real title available?)
• Statistical physics analysis of the backtrack resolution of random 3-SAT instances
• An efficient approach to solving random \(k\)-SAT problems
• An average analysis of backtracking on random constraint satisfaction problems
• Computer Science Logic
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

This page was built for publication: Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances

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