On the critical exponents of random k‐SAT

DOI10.1002/RSA.10050MaRDI QIDQ4803316zbMATH OpenOpenAlexFDO

Authors David B. Wilson

Publication date 2 April 2003

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

critical exponentrandom Boolean formulassatisfiabilitythreshold

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Abstract: There has been much recent interest in the satisfiability of random Boolean formulas. A random k-SAT formula is the conjunction of m random clauses, each of which is the disjunction of k literals (a variable or its negation). It is known that when the number of variables n is large, there is a sharp transition from satisfiability to unsatisfiability; in the case of 2-SAT this happens when m/n --> 1, for 3-SAT the critical ratio is thought to be m/n ~ 4.2. The sharpness of this transition is characterized by a critical exponent, sometimes called

u= u_k (the smaller the value of u the sharper the transition). Experiments have suggested that u_3 = 1.5+-0.1, u_4 = 1.25+-0.05, u_5=1.1+-0.05, u_6 = 1.05+-0.05, and heuristics have suggested that

u_k --> 1 as k --> infinity. We give here a simple proof that each of these exponents is at least 2 (provided the exponent is well-defined). This result holds for each of the three standard ensembles of random k-SAT formulas: m clauses selected uniformly at random without replacement, m clauses selected uniformly at random with replacement, and each clause selected with probability p independent of the other clauses. We also obtain similar results for q-colorability and the appearance of a q-core in a random graph.

Recommendations

• The scaling window of the 2-SAT transition
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))
• The asymptotic k-SAT threshold
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)

Cites work

• Almost all graphs with average degree 4 are 3-colorable
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1445295 (Why is no real title available?)

Cited in

(12)

• Random k-sat: the limiting probability for satisfiability for moderately growing k
• Structure of large random hypergraphs
• The scaling window of the 2-SAT transition
• The Normalized Autocorrelation Length of Random Max  $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Tricritical points in random combinatorics: the -SAT case
• Exact location of the phase transition for random (1,2)-QSAT
• Geometric properties of satisfying assignments of random ε-1-in-kSAT
• Satisfiability threshold for power law random 2-SAT in configuration model
• Polarised random k-SAT
• Searching for (sharp) thresholds in random structures: where are we now?
• Finite size scaling for the core of large random hypergraphs

This page was built for publication: On the critical exponents of random k‐SAT

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