Solution clustering in random satisfiability

DOI10.1140/epjb/e2008-00324-5zbMath1189.82043MaRDI 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 processes; probability theory; random models

Mathematics Subject Classification ID

82B41: Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Cites Work

• Unnamed Item
• 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
• 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