Solution clustering in random satisfiability

DOI10.1140/epjb/e2008-00324-5zbMath1189.82043OpenAlexW2077253134MaRDI QIDQ978588

Demetrios Achlioptas

Publication date: 25 June 2010

Published in: The European Physical Journal B. Condensed Matter and Complex Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1140/epjb/e2008-00324-5

zbMATH Keywords

stochastic processesprobability theoryrandom models

Mathematics Subject Classification ID

Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (3)

A Model for Phase Transition of Random Answer-Set Programs ⋮ The solution space structure of planted constraint satisfaction problems with growing domains ⋮ Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pairs of SAT-assignments in random Boolean formulæ
• Survey propagation as local equilibrium equations
• Selecting Complementary Pairs of Literals
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• Approximating the unsatisfiability threshold of random formulas
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• On the solution-space geometry of random constraint satisfaction problems
• On the solution‐space geometry of random constraint satisfaction problems
• The two possible values of the chromatic number of a random graph

This page was built for publication: Solution clustering in random satisfiability