Solution clustering in random satisfiability

DOI10.1140/EPJB/E2008-00324-5MaRDI QIDQ978588zbMATH OpenOpenAlexFDO

Authors D. 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 processesrandom modelsprobability theory

Mathematics Subject Classification ID

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

Recommendations

• Random formulas have frozen variables
• On the solution-space geometry of random constraint satisfaction problems
• On the solution-space geometry of random constraint satisfaction problems
• The set of solutions of random XORSAT formulae
• The set of solutions of random XORSAT formulae

Cites work

• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1947423 (Why is no real title available?)
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• A new look at survey propagation and its generalizations
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Approximating the unsatisfiability threshold of random formulas
• On the solution-space geometry of random constraint satisfaction problems
• On the solution-space geometry of random constraint satisfaction problems
• Pairs of SAT-assignments in random Boolean formulæ
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• Selecting Complementary Pairs of Literals
• Survey propagation as local equilibrium equations
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• The two possible values of the chromatic number of a random graph

Cited in

(18)

• Reconstruction and clustering in random constraint satisfaction problems
• Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP
• Pairs of SAT-assignments in random Boolean formulæ
• The large deviations of the whitening process in random constraint satisfaction problems
• Criticality and heterogeneity in the solution space of random constraint satisfaction problems
• On the survey-propagation equations in random constraint satisfiability problems
• Random 2-SAT solution components and a fitness landscape
• Recent Advances in Constraints
• Solution space coupling in the random \(K\)-satisfiability problem
• On the solution-space geometry of random constraint satisfaction problems
• A model for phase transition of random answer-set programs
• The set of solutions of random XORSAT formulae
• Frozen variables in random Boolean constraint satisfaction problems
• Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion
• The solution space structure of planted constraint satisfaction problems with growing domains
• The set of solutions of random XORSAT formulae
• Inside the clustering window for random linear equations
• Random formulas have frozen variables

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q978588)