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

DOI10.1016/J.TCS.2004.02.034zbMATH Open1068.68067OpenAlexW2142281466MaRDI QIDQ596103FDOQ596103

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)

Cites Work

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

Cited In (4)

• Computer Science Logic
• An efficient approach to solving random \(k\)-SAT problems
• An average analysis of backtracking on random constraint satisfaction problems
• Statistical physics analysis of the backtrack resolution of random 3-SAT instances

Recommendations

• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem 👍 👎
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat 👍 👎
• Average case results for satisfiability algorithms under the random-clause-width model 👍 👎
• An average analysis of backtracking on random constraint satisfaction problems 👍 👎
• Statistical physics analysis of the backtrack resolution of random 3-SAT instances 👍 👎
• Average Performance of Heuristics for Satisfiability 👍 👎
• Computer Science Logic 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

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)