Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances
From MaRDI portal
Publication:596103
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
- 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
- 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?)
- Lower bounds for random 3-SAT via differential equations
- Many hard examples for resolution
- Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
- Probabilistic Analysis of Two Heuristics for the 3-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
- An average analysis of backtracking on random constraint satisfaction problems
- Statistical physics analysis of the backtrack resolution of random 3-SAT instances
- scientific article; zbMATH DE number 2080304 (Why is no real title available?)
- Computer Science Logic
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- An efficient approach to solving random \(k\)-SAT problems
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)
