Threshold values of random K‐SAT from the cavity method

Using the cavity equations of Mézard, Parisi, and Zecchina Science 297 (2002), 812 ; Mézard and Zecchina, Phys Rev E 66 (2002), 056126 we derive the various threshold values for the number of clauses per variable of the random K‐satisfiability problem, generalizing the previous results to K ≥ 4. We also give an analytic solution of the equations, and some closed expressions for these thresholds, in an expansion around large K. The stability of the solution is also computed. For any K, the satisfiability threshold is found to be in the stable region of the solution, which adds further credit to the conjecture that this computation gives the exact satisfiability threshold.© 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006

• Publication year

  2003

• Venue

  Random Struct. Algorithms

• Publication date

  2003-09-12

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1002/rsa.20090arXiv cs/0309020
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• THE THRESHOLD FOR RANDOM k-SAT IS 2 log 2−O(k)

  2004cited by this paper
• Instability of one-step replica-symmetry-broken phase in satisfiability problems

  2003cited by this paper
• Supersymmetric Higgs production at the large hadron collider

  2003cited by this paper
• Two Solutions to Diluted p-Spin Models and XORSAT Problems

  2003cited by this paper
• Phase diagram of random heteropolymers.

  2003cited by this paper
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses

  2003influential reference
• Survey propagation as local equilibrium equations

  2003cited by this paper
• The Thermodynamic Limit in Mean Field Spin Glass Models

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

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

  2002cited by this paper
• Survey propagation: An algorithm for satisfiability

  2002influential reference
• Analytic and Algorithmic Solution of Random Satisfiability Problems

  2002cited by this paper
• Lower bounds for random 3-SAT via differential equations

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

  2001cited by this paper
• Simplest random K-satisfiability problem

  2000cited by this paper
• Sharp thresholds of graph properties, and the -sat problem

  1999cited by this paper
• Determining computational complexity from characteristic ‘phase transitions’

  1999cited by this paper
• Approximating the unsatisfiability threshold of random formulas

  1998cited by this paper
• A General Upper Bound for the Satisfiability Threshold of Random r-SAT Formulae

  1997influential reference
• Finding Hard Instances of the Satissability Problem: a Survey

  1997cited by this paper
• Analysis of Two Simple Heuristics on a Random Instance of k-SAT

  1996cited 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
• Average Case Completeness

  1991cited by this paper
• On the theory of average case complexity

  1989cited by this paper
• Spin Glass Theory and Beyond

  1987cited by this paper
• Average Case Complete Problems

  1986cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• The complexity of theorem-proving procedures

  1971cited by this paper

• Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems

  2026cites this paper
• Concept learning for algorithmic reasoning: Insights from SAT-solving GNNs

  2026cites this paper
• Empirical Impact of Dimensionality on Random Geometric SAT

  2026influential citation
• The value of random zero-sum games

  2026cites this paper
• Algorithmic thresholds in combinatorial optimization depend on the time scaling

  2025influential citation
• A CLuP algorithm to practically achieve ∼ 0.76 SK–model ground state free energy

  2025cites this paper
• Local equations describe unreasonably efficient stochastic algorithms in random K-SAT.

  2025cites this paper
• Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition

  2025influential citation
• Interacting copies of random-constraint satisfaction problems.

  2025cites this paper
• Iterated entropy derivatives and binary entropy inequalities

  2025cites this paper
• A Geometric Perspective on the Difficulties of Learning GNN-based SAT Solvers

  2025influential citation
• Sampled-Based Guided Quantum Walk: Non-variational quantum algorithm for combinatorial optimization

  2025cites this paper
• Can Large Language Models Reason? A Characterization via 3-SAT

  2024cites this paper
• Searching for (sharp) thresholds in random structures: Where are we now?

  2024cites this paper
• Concept Learning in the Wild: Towards Algorithmic Understanding of Neural Networks

  2024cites this paper
• Parallel tempering–inspired distributed binary optimization with in-memory computing

  2024cites this paper
• Solving Boolean Satisfiability Problems With The Quantum Approximate Optimization Algorithm

  2024cites this paper
• Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains*

  2024cites this paper
• Assessing and advancing the potential of quantum computing: A NASA case study

  2024cites this paper
• CHAMP: A multipass algorithm for Max Sat based on saver variables

  2023cites this paper
• Studying Hopfield models via fully lifted random duality theory

  2023cites this paper
• Generic proving of replica symmetry breaking

  2023cites this paper
• Upper bounds on the 2-colorability threshold of random d-regular k-uniform hypergraphs for k≥3

  2023cites this paper
• Polarised random -SAT

  2023cites this paper
• Local Optima Markov Chain: A New Tool for Landscape-aware Analysis of Algorithm Dynamics

  2023cites this paper
• An Introduction to the Theory of Spin Glasses

  2023cites this paper
• Iterated Entropy Derivatives and Binary Entropy Inequalities

  2023cites this paper
• A residual-based message passing algorithm for constraint satisfaction problems

  2022cites this paper
• GO-MOCE: Greedy Order Method of Conditional Expectations for Max Sat

  2022cites this paper
• Polarised random k-SAT

  2022influential citation
• Using the method of conditional expectations to supply an improved starting point for CCLS

  2022cites this paper
• Toward an Understanding of Long-tailed Runtimes of SLS Algorithms

  2022cites this paper
• Why adiabatic quantum annealing is unlikely to yield speed-up

  2022cites this paper
• A Novel Algorithm for Max Sat Calling MOCE to Order

  2021cites this paper
• A New Method for 3-Satisfiability Problem Solving Space Structure on Structural Entropy

  2021influential citation
• The Phase Transition Analysis for the Random Regular Exact 2-(d, k)-SAT Problem

  2021cites this paper
• ISSATA: An algorithm for solving the 3-satisfiability problem based on improved strategy

  2021cites this paper
• Evidence for Long-Tails in SLS Algorithms

  2021cites this paper
• Certifying solution geometry in random CSPs: counts, clusters and balance

  2021cites this paper
• Probabilistic characterization of random Max r-Sat

  2021cites this paper
• The Phase Transition Analysis for Random Regular Exact (s, c, k)—SAT Problem

  2021cites this paper
• Incomplete Algorithms

  2021cites this paper
• Entropic barriers as a reason for hardness in both classical and quantum algorithms

  2021cites this paper
• A New Method for 3-Satisfiability Problem Phase Transition on Structural Entropy

  2021cites this paper
• Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion

  2020cites this paper
• Generating Difficult CNF Instances in Unexplored Constrainedness Regions

  2020cites this paper
• On the Effect of Learned Clauses on Stochastic Local Search

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

  2020cites this paper
• Maximally flexible solutions of a random K-satisfiability formula.

  2020cites this paper
• Effect of Initial Assignment on Local Search Performance for Max Sat

  2020cites this paper
• The Asymptotics of the Clustering Transition for Random Constraint Satisfaction Problems

  2019cites this paper
• Graphical representation and hierarchical decomposition mechanism for vertex-cover solution space

  2019cites this paper
• Generating Difficult SAT Instances by Preventing Triangles

  2019cites this paper
• Adaptation, fitness landscape learning and fast evolution

  2019cites this paper
• Warning Propagation Algorithm for the MAX-3-SAT Problem

  2019cites this paper
• An Effective FPGA Solver on Probability Distribution and Preprocessing

  2019cites this paper
• Hierarchical Decomposition Mechanism by König-Egérvary Layer-Subgraph with Application on Vertex-Cover

  2019cites this paper
• A Model of Random Industrial SAT

  2019cites this paper
• Applying quantum algorithms to constraint satisfaction problems

  2018cites this paper
• The threshold for SDP-refutation of random regular NAE-3SAT

  2018cites this paper
• On the Satisfiability Threshold of Random Community-Structured SAT

  2018cites this paper
• Approximate survey propagation for statistical inference

  2018cites this paper
• FPGA-based satisfiability filters for deep packet inspection

  2018cites this paper
• A high-performance analog Max-SAT solver and its application to Ramsey numbers

  2018cites this paper
• A continuous-time MaxSAT solver with high analog performance

  2018cites this paper
• Talk Notes (First Half)

  2018cites this paper
• Biased landscapes for random constraint satisfaction problems

  2018cites this paper
• The Hard Problems Are Almost Everywhere For Random CNF-XOR Formulas

  2017cites this paper
• Quantum computational supremacy

  2017cites this paper
• Phase transitions in the q-coloring of random hypergraphs

  2017influential citation
• A hybrid encryption scheme based on the satisfiability problem

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

  2017cites this paper
• Belief Propagation Guided Decimation Fails on Random Formulas

  2017cites this paper
• Sufficient conditions for convergence of the survey propagation algorithm

  2017cites this paper
• Revisiting the cavity-method threshold for random 3-SAT.

  2017cites this paper
• Optimising power flow in a volatile electrical grid using a message passing algorithm

  2017cites this paper
• Complexity Analysis of Mixed Constraint Satisfaction Problems

  2017cites this paper
• Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods

  2017cites this paper
• Analysing Survey Propagation Guided Decimation on Random Formulas

  2016cites this paper
• The large deviations of the whitening process in random constraint satisfaction problems

  2016cites this paper
• Solutions to the Problem of K-SAT / K-COL Phase Transition Location

  2016cites this paper
• Beyond the structure of SAT formulas

  2016cites this paper
• The Normalized Autocorrelation Length of Random Max r -Sat Converges in Probability to (1-1/2^r)/r

  2016cites this paper
• Assessment of Quantum Annealing for the Construction of Satisfiability Filters

  2016cites this paper
• On the K‐sat model with large number of clauses

  2016cites this paper
• Local Search for Hard SAT Formulas: The Strength of the Polynomial Law

  2016cites this paper
• The number of solutions for random regular NAE-SAT

  2016cites this paper
• UPPER BOUND ON THE SATISFIABILITY THRESHOLD OF REGULAR RANDOM ( k , s )-SAT PROBLEM

  2016influential citation
• On the Empirical Time Complexity of Random 3-SAT at the Phase Transition

  2015influential citation
• The backtracking survey propagation algorithm for solving random K-SAT problems

  2015cites this paper
• Research on solution space of bipartite graph vertex-cover by maximum matchings

  2015cites this paper
• Overview and analysis of the SAT Challenge 2012 solver competition

  2015cites this paper
• Analysing the empirical time complexity of high-performance algorithms for SAT and TSP

  2015cites this paper
• Proof of the Satisfiability Conjecture for Large k

  2014cites this paper
• The Cavity Method in Coding Theory

  2014cites this paper
• 1 The Sherrington-Kirkpatrick model

  2014cites this paper
• Punctuated evolution and robustness in morphogenesis

  2014cites this paper
• Introduction to the SK model

  2014cites this paper
• Double Configuration Checking in Stochastic Local Search for Satisfiability

  2014cites this paper
• Organization mechanism and counting algorithm on vertex-cover solutions

  2014cites this paper