On the Probabilistic Approach to the Random Satisfiability Problem

In this note I will review some of the recent results that have been obtained in the probabilistic approach to the random satisfiability problem. At the present moment the results are only heuristic. In the case of the random 3-satisfiability problem a phase transition from the satisfiable to the unsatisfiable phase is found at α=4.267. There are other values of α that separates different regimes and they will be described in details. In this context the properties of the survey decimation algorithm will also be discussed.

• Publication year

  2003

• Venue

  International Conference on Theory and Applications of Satisfiability Testing

• Publication date

  2003-05-05

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1007/978-3-540-24605-3_16arXiv cs/0308010
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Survey propagation: An algorithm for satisfiability

  2005cited by this paper
• Some remarks on the survey decimation algorithm for K-satisfiability

  2003cited by this paper
• Random K-satisfiability problem: from an analytic solution to an efficient algorithm.

  2002cited by this paper
• Replica Bounds for Optimization Problems and Diluted Spin Systems

  2002influential reference
• Survey propagation: An algorithm for satisfiability

  2002cited by this paper
• La maladie d'Alzheimer

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

  2002cited by this paper
• Coloring random graphs

  2002cited by this paper
• The Cavity Method at Zero Temperature

  2002cited by this paper
• Rigorous decimation-based construction of ground pure states for spin-glass models on random lattices.

  2002cited by this paper
• On local equilibrium equations for clustering states

  2002cited by this paper
• Phase transitions in combinatorial problems

  2001cited by this paper
• Factor graphs and the sum-product algorithm

  2001cited by this paper
• The zeta(2) limit in the random assignment problem

  2000cited by this paper
• THE EUROPEAN PHYSICAL JOURNAL B c○ EDP Sciences

  2000cited by this paper
• Typical random 3-SAT formulae and the satisfiability threshold

  2000cited by this paper
• Generalized Belief Propagation

  2000cited by this paper
• The ζ(2) limit in the random assignment problem

  2000cited by this paper
• The Bethe lattice spin glass revisited

  2000cited by this paper
• Rigorous low-temperature results for the mean field p-spins interaction model

  2000cited by this paper
• Finding Hard Instances of the Satissability Problem: a Survey

  1997cited by this paper
• Entropy of the K-satisfiability problem.

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

  1994cited by this paper
• Replica symmetry breaking in finite connectivity systems: a large connectivity expansion at finite and zero temperature

  1989cited by this paper
• Spin Glass Theory and Beyond

  1987influential reference
• Solution of 'Solvable model of a spin glass'

  1977cited by this paper

• Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems

  2026cites this paper
• Where do hard problems really exist?

  2023cites this paper
• Learning from survey propagation: a neural network for MAX-E-3-SAT

  2020cites this paper
• Bee colony optimization for the satisfiability problem in probabilistic logic

  2015cites this paper
• Some results for k-SAT on trees

  2015cites this paper
• On Sparse Discretization for Graphical Games

  2014cites this paper
• On the survey-propagation equations in random constraint satisfiability problems

  2008cites this paper
• Statistical mechanics of optimization problems

  2006cites this paper
• PERIODIC ATTRACTORS OF RANDOM TRUNCATOR MAPS

  2006cites this paper
• Comparing Beliefs, Surveys, and Random Walks

  2004cites this paper
• Constraint Optimization and Statistical Mechanics

  2003cites this paper