Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances
From MaRDI portal
Publication:596103
DOI10.1016/J.TCS.2004.02.034zbMATH Open1068.68067OpenAlexW2142281466MaRDI QIDQ596103FDOQ596103
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
Recommendations
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
- An average analysis of backtracking on random constraint satisfaction problems
- scientific article
- 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
- Publication:4952608
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorial probability (60C05)
Cites Work
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Analysis of Two Simple Heuristics on a Random Instance ofk-sat
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The dynamics of proving uncolourability of large random graphs: I. Symmetric colouring heuristic
- Lower bounds for random 3-SAT via differential equations
- Title not available (Why is that?)
- Statistical mechanics methods and phase transitions in optimization problems
- SAT2000. Highlights of satisfiability research in the year 2000. 3rd international workshop, September 1998
- Title not available (Why is that?)
- A sharp threshold in proof complexity
- Rigorous results for random (\(2+p)\)-SAT
- Results related to threshold phenomena research in satisfiability: Lower bounds
Cited In (7)
- Computer Science Logic
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- An efficient approach to solving random \(k\)-SAT problems
- Title not available (Why is that?)
- 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
- An average analysis of backtracking on random constraint satisfaction problems
- Statistical physics analysis of the backtrack resolution of random 3-SAT instances
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)
