On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
From MaRDI portal
Publication:955013
DOI10.1016/j.tcs.2008.06.053zbMath1152.68052WikidataQ125756943 ScholiaQ125756943MaRDI QIDQ955013
Alistair Sinclair, Elitza Maneva
Publication date: 18 November 2008
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2008.06.053
phase transitions; random 3-SAT; first-moment method; survey propagation; threshold of satisfiability
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
Using sequential runtime distributions for the parallel speedup prediction of SAT local search, Satisfiability threshold for random regular \textsc{nae-sat}, Upper-bounding the \(k\)-colorability threshold by counting covers, The cook-book approach to the differential equation method, Estimating satisfiability, The asymptotic \(k\)-SAT threshold, Pruning processes and a new characterization of convex geometries, On the satisfiability threshold of formulas with three literals per clause, Large-scale parallelism for constraint-based local search: the costas array case study
Cites Work
- Unnamed Item
- Unnamed Item
- Pruning processes and a new characterization of convex geometries
- The unsatisfiability threshold revisited
- Survey propagation as local equilibrium equations
- Almost all graphs with 1.44n edges are 3-colorable
- A new look at survey propagation and its generalizations
- Approximating the unsatisfiability threshold of random formulas
- Sharp thresholds of graph properties, and the $k$-sat problem
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
- Bounding the unsatisfiability threshold of random 3-SAT
- Tail bounds for occupancy and the satisfiability threshold conjecture
- The probabilistic analysis of a greedy satisfiability algorithm
- On the solution-space geometry of random constraint satisfaction problems
