Proof of the satisfiability conjecture for large k

DOI10.1145/2746539.2746619MaRDI QIDQ2941489zbMATHOpenAlexFDO

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)

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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}_{\ast }(k)$ such that a random $k$-SAT formula of clause density $alpha$ is with high probability satisfiable for $alpha<alph{a}_{\ast }$, and unsatisfiable for $alpha>alph{a}_{\ast }$. We show that the threshold $alph{a}_{\ast }(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.

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

Cites work

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

Cited in

(71)

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

Describes a project that uses

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)