Proof of the satisfiability conjecture for large k

DOI10.1145/2746539.2746619zbMATH Open1321.68304arXiv1411.0650OpenAlexW2070702809MaRDI QIDQ2941489FDOQ2941489

Authors: Jian Ding, Allan Sly, Nike Sun 

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Abstract: We establish the satisfiability threshold for random $k$-SAT for all $kge{k}_0$, with $k_0$ an absolute constant. That is, there exists a limiting density $alph{a}_{*}(k)$ such that a random $k$-SAT formula of clause density $alpha$ is with high probability satisfiable for $alpha<alph{a}_{*}$, and unsatisfiable for $alpha>alph{a}_{*}$. We show that the threshold $alph{a}_{*}(k)$ is given explicitly by the one-step replica symmetry breaking prediction from statistical physics. The proof develops a new analytic method for moment calculations on random graphs, mapping a high-dimensional optimization problem to a more tractable problem of analyzing tree recursions. We believe that our method may apply to a range of random CSPs in the 1-RSB universality class.

Full work available at URL: https://arxiv.org/abs/1411.0650

Recommendations

• Proof of the satisfiability conjecture for large \(k\)
• The asymptotic \(k\)-SAT threshold
• Satisfiability threshold for random regular NAE-SAT
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold

zbMATH Keywords

condensationconstraint satisfaction problembelief propagationreplica symmetry breakingrandom \(k\)-SATsurvey propagationsatisfiability threshold

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Shortest-path queries in static networks
• Approximate distance oracles
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On approximate distance labels and routing schemes with affine stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Approximate distance oracles with constant query time
• Fast C-K-R partitions of sparse graphs
• Automata, Languages and Programming
• Ramsey partitions and proximity data structures

Cited In (70)

• On the concentration of the number of solutions of random satisfiability formulas
• Spin systems on Bethe lattices
• Super solutions of random \((3 + p)\)-SAT
• Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
• Title not available (Why is that?)
• Storage capacity in symmetric binary perceptrons
• Bethe states of random factor graphs
• On the spectral gap of spherical spin glass dynamics
• The satisfiability threshold for a seemingly intractable random constraint satisfaction problem
• On the K‐sat model with large number of clauses
• Title not available (Why is that?)
• The satisfiability threshold for random linear equations
• A model of random industrial SAT
• Information-theoretic thresholds from the cavity method
• Phase transitions in discrete structures
• Optimal testing for planted satisfiability problems
• Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Charting the replica symmetric phase
• Satisfiability threshold for random regular \textsc{nae-sat}
• Constraining the clustering transition for colorings of sparse random graphs
• Constructing concrete hard instances of the maximum independent set problem
• The replica symmetric phase of random constraint satisfaction problems
• Walksat Stalls Well Below Satisfiability
• Belief propagation for the maximum-weight independent set and minimum spanning tree problems
• Bose-Einstein condensation in satisfiability problems
• Speed and concentration of the covering time for structured coupon collectors
• Random subcube intersection graphs. I: Cliques and covering
• Local minima in disordered mean-field ferromagnets
• Charting the replica symmetric phase
• Satisfiability threshold for random regular NAE-SAT
• Counting Solutions to Random CNF Formulas
• Probabilistic characterization of random Max \(r\)-Sat
• Decoding from Pooled Data: Sharp Information-Theoretic Bounds
• Waiter-client and client-waiter colourability and \(k\)-SAT games
• The asymptotic \(k\)-SAT threshold
• The \(K\)-SAT problem in a simple limit
• The asymptotics of the clustering transition for random constraint satisfaction problems
• The asymptotic \(k\)-SAT threshold
• The number of satisfying assignments of random regular \(k\)-SAT formulas
• Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion
• Proof Complexity for the Maximum Satisfiability Problem and its Use in SAT Refutations
• Harnessing the Bethe free energy
• New models for generating hard random Boolean formulas and disjunctive logic programs
• The number of satisfying assignments of random 2‐SAT formulas
• Threshold values of random K‐SAT from the cavity method
• Title not available (Why is that?)
• CHAMP: a multipass algorithm for Max Sat based on saver variables
• The number of solutions for random regular NAE-SAT
• Biased landscapes for random constraint satisfaction problems
• Go-MOCE: greedy order method of conditional expectations for Max Sat
• The potential of quantum annealing for rapid solution structure identification
• The high temperature case for the random \(K\)-sat problem
• Satisfiability Decay along Conjunctions of Pseudo-Random Clauses
• The stripping process can be slow. II
• Zero-temperature dynamics in the dilute Curie-Weiss model
• Satisfiability threshold for power law random 2-SAT in configuration model
• Title not available (Why is that?)
• Lower bounds on the chromatic number of random graphs
• Belief propagation on the random \(k\)-SAT model
• Using the method of conditional expectations to supply an improved starting point for CCLS
• Streamlining variational inference for constraint satisfaction problems
• On Super Strong ETH
• Critical window of the symmetric perceptron
• Biased random k‐SAT
• Polarised random \(k\)-SAT
• Sharp thresholds in adaptive random graph processes
• Combinatorial statistics and the sciences
• Ultrametricity in spin glasses
• One-step replica symmetry breaking of random regular NAE-SAT. II

Uses Software

• Graphs

This page was built for publication: Proof of the satisfiability conjecture for large \(k\)

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