The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)

DOI10.1090/S0894-0347-04-00464-3MaRDI QIDQ4821034zbMATH OpenOpenAlexFDO

Authors Yuval Peres, D. Achlioptas

Publication date 7 October 2004

Published in Journal of the American Mathematical Society (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Boolean functions (06E30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: Let F be a random k-SAT formula on n variables, formed by selecting uniformly and independently m = rn out of all possible k-clauses. It is well-known that if r>2^k ln 2, then the formula F is unsatisfiable with probability that tends to 1 as n tends to infinity. We prove that there exists a sequence t_k = O(k) such that if r < 2^k ln 2 - t_k, then the formula F is satisfiable with probability that tends to 1 as n tends to infinity. Our technique yields an explicit lower bound for the random k-SAT threshold for every k. For k>3 this improves upon all previously known lower bounds. For example, when k=10 our lower bound is 704.94 while the upper bound is 708.94.

Recommendations

• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))
• Random k-SAT: A tight threshold for moderately growing k
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random \(k\)-SAT
• A sharp threshold for a random constraint satisfaction problem

Cites work

• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Approximating the unsatisfiability threshold of random formulas
• Bounding the unsatisfiability threshold of random 3-SAT
• scientific article; zbMATH DE number 3886512 (Why is no real title available?)
• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1158743 (Why is no real title available?)
• scientific article; zbMATH DE number 1947423 (Why is no real title available?)
• scientific article; zbMATH DE number 1445295 (Why is no real title available?)
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Random k-SAT: A tight threshold for moderately growing k
• Sharp thresholds of graph properties, and the k-sat problem
• Some problems concerning the structure of random walk paths
• Survey propagation: An algorithm for satisfiability
• Thick points for planar Brownian motion and the Erdős-Taylor conjecture on random walk

Cited in

(only showing first 100 items - show all)

• Phase transitions in discrete structures
• Sharpness of the satisfiability threshold for non-uniform random \(k\)-SAT
• Charting the replica symmetric phase
• On the lower bounds of random Max 3 and 4-SAT
• A sharp threshold for a random constraint satisfaction problem
• A tighter upper bound for random MAX \(2\)-SAT
• Spin systems on Bethe lattices
• Probabilistic characterization of random Max r-Sat
• Belief propagation on the random \(k\)-SAT model
• Using the method of conditional expectations to supply an improved starting point for CCLS
• A model of random industrial SAT
• Proof of the satisfiability conjecture for large \(k\)
• Percolation on fitness landscapes: effects of correlation, phenotype, and incompatibilities
• Optimal testing for planted satisfiability problems
• Super solutions of random \((3 + p)\)-SAT
• On the hardness of solving edge matching puzzles as SAT or CSP problems
• Waiter-client and client-waiter colourability and \(k\)-SAT games
• Random k-SAT: A tight threshold for moderately growing k
• Pairs of SAT-assignments in random Boolean formulæ
• The structure of the set of satisfying assignments for a random \(k\)-CNF
• An algorithm for random signed 3-SAT with intervals
• CHAMP: a multipass algorithm for Max Sat based on saver variables
• Go-MOCE: greedy order method of conditional expectations for Max Sat
• Thresholds for colourability and satisfiability in random graphs and Boolean formulae
• The Normalized Autocorrelation Length of Random Max  $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$
• The power of choice for random satisfiability
• On the number of circuits in random graphs
• On the concentration of the number of solutions of random satisfiability formulas
• Proof of the satisfiability conjecture for large k
• Harnessing the Bethe free energy
• The decimation process in random k-SAT
• Independent sets in random graphs from the weighted second moment method
• On the diameter of the set of satisfying assignments in random satisfiable k-CNF formulas
• Random \(\mathbb{Z}^d\)-shifts of finite type
• The number of satisfying assignments of random regular k-SAT formulas
• Random k-SAT and the power of two choices
• The large deviations of the whitening process in random constraint satisfaction problems
• On smoothed analysis in dense graphs and formulas
• Satisfiability Decay along Conjunctions of Pseudo-Random Clauses
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Lower and Upper Bounds for Random Mimimum Satisfiability Problem
• Random instances of problems in NP -- algorithms and statistical physics
• On the maximum satisfiability of random formulas
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• A note on random \(k\)-SAT for moderately growing \(k\)
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• On the Lower Bounds of Random Max 3 and 4-SAT
• On the critical exponents of random k‐SAT
• Bounds on threshold of regular random k-SAT
• Branching process approach for 2-SAT thresholds
• Geometrical organization of solutions to random linear Boolean equations
• The replica symmetric phase of random constraint satisfaction problems
• Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random \(k\)-SAT
• Information-theoretic and algorithmic thresholds for group testing
• Bounds on the satisfiability threshold for power law distributed random SAT
• Constructing concrete hard instances of the maximum independent set problem
• On the phase transitions of (k, q)-SAT
• Walksat Stalls Well Below Satisfiability
• Cores in random hypergraphs and Boolean formulas
• Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
• On the lower bounds of \((1, 0)\)-super solutions for random \(k\)-SAT
• A new upper bound for random (2 + p)-SAT by flipping two variables
• On an online random k‐SAT model
• A lower bound for the 4-satisfiability threshold
• Threshold values of random K‐SAT from the cavity method
• The pure literal rule threshold and cores in random hypergraphs
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Theory and Applications of Satisfiability Testing
• The condensation transition in random hypergraph 2-coloring
• The set of solutions of random XORSAT formulae
• Streamlining variational inference for constraint satisfaction problems
• Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion
• Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
• On the solution-space geometry of random constraint satisfaction problems
• Theory and Applications of Models of Computation
• Certifying unsatisfiability of random 2k-SAT formulas using approximation techniques.
• Lower bounds for random 3-SAT via differential equations
• Upper bounds on the satisfiability threshold
• Satisfiability threshold for random regular \textsc{nae-sat}
• Free energy subadditivity for symmetric random Hamiltonians
• The number of satisfying assignments of random 2‐SAT formulas
• Biased random k‐SAT
• The discrepancy of random rectangular matrices
• What is the satisfiability threshold of random balanced Boolean expressions?
• Digital collections of examples in mathematical sciences
• One-step replica symmetry breaking of random regular NAE-SAT. II
• On the thresholds in linear and nonlinear Boolean equations
• The mean field traveling salesman and related problems
• Analysis of local search landscapes for \(k\)-SAT instances
• Polarised random k-SAT
• A threshold for unsatisfiability
• \texttt{WalkSAT} is linear on random 2-SAT
• Upper bounds on the 2-colorability threshold of random d-regular k-uniform hypergraphs for k 3
• The number of random 2-SAT solutions is asymptotically log-normal
• A CLuP algorithm to practically achieve 0.76 SK-model ground state free energy
• On the satisfiability of random 3-SAT formulas with \(k\)-wise independent clauses
• The set of solutions of random XORSAT formulae
• Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
• On threshold properties of k-SAT: An additive viewpoint

This page was built for publication: The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)

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