The Scaling Window of the 2-SAT Transition

Abstract

We consider the random 2-satisfiability problem, in which each instance is a formula that is the conjunction of m clauses of the form (x or y), chosen uniformly at random from among all 2-clauses on n Boolean variables and their negations. As m and n tend to infinity in the ratio m/n --> alpha, the problem is known to have a phase transition at alpha_c = 1, below which the probability that the formula is satisfiable tends to one and above which it tends to zero. We determine the finite-size scaling about this transition, namely the scaling of the maximal window W(n,delta) = (alpha_-(n,delta),alpha_+(n,delta)) such that the probability of satisfiability is greater than 1-delta for alpha < alpha_- and is less than delta for alpha > alpha_+. We show that W(n,delta)=(1-Theta(n^{-1/3}),1+Theta(n^{-1/3})), where the constants implicit in Theta depend on delta. We also determine the rates at which the probability of satisfiability approaches one and zero at the boundaries of the window. Namely, for m=(1+epsilon)n, where epsilon may depend on n as long as |epsilon| is sufficiently small and |epsilon|*n^(1/3) is sufficiently large, we show that the probability of satisfiability decays like exp(-Theta(n*epsilon^3)) above the window, and goes to one like 1-Theta(1/(n*|epsilon|^3)) below the window. We prove these results by defining an order parameter for the transition and establishing its scaling behavior in n both inside and outside the window. Using this order parameter, we prove that the 2-SAT phase transition is continuous with an order parameter critical exponent of 1. We also determine the values of two other critical exponents, showing that the exponents of 2-SAT are identical to those of the random graph.

57 pages. This version updates some references

References in corpus (3)

• The Scaling Window of the 2-SAT Transition
• Statistical mechanics of the random K-SAT model
• Typical random 3-SAT formulae and the satisfiability threshold

Cited by in corpus (46)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• The Scaling Window of the 2-SAT Transition
• Probing for quantum speedup in spin glass problems with planted solutions
• Typical random 3-SAT formulae and the satisfiability threshold
• Exact solutions for diluted spin glasses and optimization problems
• Kinetic Theory of Random Graphs: from Paths to Cycles
• Extremal Optimization at the Phase Transition of the 3-Coloring Problem
• The Satisfiability Threshold of Random 3-SAT Is at Least 3.52
• Finite size scaling for the core of large random hypergraphs
• MAX 2-SAT with up to 108 qubits
• Random MAX SAT, Random MAX CUT, and Their Phase Transitions
• Threshold for monotone symmetric properties through a logarithmic Sobolev inequality
• Percolation with Multiple Giant Clusters
• A Quantum Lovasz Local Lemma
• Phase Transition with Non-Thermodynamic States in Reversible Polymerization
• Kinetics of First Passage in a Cone
• Computational hardness of spin-glass problems with tile-planted solutions
• On the critical exponents of random k-SAT
• The random 2-SAT partition function
• Scaling Behavior of Threshold Epidemics
• Criticality and Universality in the Unit-Propagation Search Rule
• Dynamics of Random Graphs with Bounded Degrees
• Cluster expansions in dilute systems: applications to satisfiability problems and spin glasses
• Computational Complexity and Phase Transitions
• Kinetics of Ring Formation
• Gibbs Measures and Phase Transitions on Sparse Random Graphs
• Scale-Free Random SAT Instances
• Finding cores of random 2-SAT formulae via Poisson cloning
• On Sharp Thresholds in Random Geometric Graphs
• Critical behaviour of combinatorial search algorithms, and the unitary-propagation universality class
• Revisiting the cavity-method threshold for random 3-SAT
• Phase Transitions and all that
• How frequently is a system of 2-linear Boolean equations solvable?
• Percolation of satisfiability in finite dimensions
• Quantum Searches in a Hard 2SAT Ensemble
• On the satisfability of random k-Horn formulae
• On the probability of planarity of a random graph near the critical point
• Inside the clustering threshold for random linear equations
• The threshold for random (1,2)-QSAT
• Classical-Quantum Mixing in the Random 2-Satisfiability Problem
• Biased random k-SAT
• On the Scaling Window of Model RB
• A Phase Transition and Stochastic Domination in Pippenger's Probabilistic Failure Model for Boolean Networks with Unreliable Gates
• Concentration Inequalities for Branching Random Walks with Applications to Phase Transitions in CSPs
• Satisfying assignments of Random Boolean CSP: Clusters and Overlaps
• A Model of Random Industrial SAT