Exhaustive enumeration unveils clustering and freezing in random 3-SAT

We study geometrical properties of the complete set of solutions of the random 3-satisfiability problem. We show that even for moderate system sizes the number of clusters corresponds surprisingly well with the theoretic asymptotic prediction. We locate the freezing transition in the space of solutions, which has been conjectured to be relevant in explaining the onset of computational hardness in random constraint satisfaction problems.

• Publication year

  2008

• Venue

  Physical review. E, Statistical, nonlinear, and soft matter physics

• Publication date

  2008-04-02

• Fields of study

  Mathematics, Physics, Computer Science, Medicine

• Identifiers
  DOI 10.1103/PhysRevE.78.040101arXiv 0804.0362PMID 18999364
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems

  2008cited by this paper
• Phase Transitions in the Coloring of Random Graphs

  2007cited by this paper
• A Landscape Analysis of Constraint Satisfaction Problems

  2007cited by this paper
• Gibbs states and the set of solutions of random constraint satisfaction problems

  2006cited by this paper
• Behavior of heuristics on large and hard satisfiability problems.

  2006cited by this paper
• Clustering of solutions in the random satisfiability problem

  2005cited by this paper
• Analytic and Algorithmic Solution of Random Satisfiability Problems

  2002cited by this paper
• Critical Behavior in the Satisfiability of Random Boolean Expressions

  1994cited by this paper
• Spin Glass Theory and Beyond

  1987cited by this paper
• private communication

  1983cited by this paper

• Complete realization of energy landscapes and non-equilibrium trapping dynamics in small spin glass and optimization problems

  2024cites this paper
• Energy landscapes of combinatorial optimization in Ising machines.

  2024cites this paper
• Cutting-plane algorithms and solution whitening for the vertex-cover problem.

  2022cites this paper
• Understanding the computational difficulty of a binary-weight perceptron and the advantage of input sparseness

  2019cites this paper
• Phase transitions of the typical algorithmic complexity of the random satisfiability problem studied with linear programming

  2017cites this paper
• Order-to-chaos transition in the hardness of random Boolean satisfiability problems

  2016cites this paper
• The backtracking survey propagation algorithm for solving random K-SAT problems

  2015cites this paper
• Solution Space Coupling in the Random K-Satisfiability Problem

  2013cites this paper
• Reweighted Belief Propagation and Quiet Planting for Random K-SAT

  2012cites this paper
• Analytical and belief-propagation studies of random constraint satisfaction problems with growing domains.

  2012cites this paper
• A message-passing approach to random constraint satisfaction problems with growing domains

  2011cites this paper
• On the solution‐space geometry of random constraint satisfaction problems

  2011cites this paper
• Numerical solution-space analysis of satisfiability problems.

  2010cites this paper
• Algebraic characteristics and satisfiability threshold of random Boolean equations.

  2010cites this paper
• On belief propagation guided decimation for random k-SAT

  2010cites this paper
• Learning by random walks in the weight space of the Ising perceptron

  2010cites this paper
• Solution space heterogeneity of the random $K$-satisfiability problem: Theory and simulations

  2010cites this paper
• A Better Algorithm for Random k-SAT

  2009cites this paper
• Communities of solutions in single solution clusters of a random K-satisfiability formula.

  2009cites this paper
• Random Constraint Satisfaction Problems

  2009cites this paper
• Weight space structure and analysis using a finite replica number in the Ising perceptron

  2009cites this paper
• Glassy behavior and jamming of a random walk process for sequentially satisfying a constraint satisfaction formula

  2009cites this paper
• Statistical and algebraic analysis of a family of random Boolean equations

  2009cites this paper
• From one solution of a 3-satisfiability formula to a solution cluster: frozen variables and entropy.

  2008cites this paper
• Constraint satisfaction problems with isolated solutions are hard

  2008cites this paper
• T-->0 mean-field population dynamics approach for the random 3-satisfiability problem.

  2007cites this paper
• On the solution-space geometry of random constraint satisfaction problems

  2006cites this paper