Random \(k\)-SAT: A tight threshold for moderately growing \(k\)

DOI10.1007/s00493-005-0017-3zbMath1083.68048WikidataQ57401508 ScholiaQ57401508MaRDI QIDQ2387184

Nicholas C. Wormald, Alan M. Frieze

Publication date: 26 January 2006

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-005-0017-3

zbMATH Keywords

second moment method; random \(k\)-SAT; tight threshold

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05D40: Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)

Related Items

The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘), Speed and concentration of the covering time for structured coupon collectors, On the Lower Bounds of (1,0)-Super Solutions for Random k-SAT, Bounding the scaling window of random constraint satisfaction problems, The condensation transition in random hypergraph 2-coloring, Biased random k‐SAT, The discrepancy of random rectangular matrices, A general model and thresholds for random constraint satisfaction problems, On the phase transitions of \((k, q)\)-SAT, On the phase transitions of random \(k\)-constraint satisfaction problems, Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT, The scaling window of the model \(d\)-\(k\)-CSP, The asymptotic \(k\)-SAT threshold, A sharp threshold for a random constraint satisfaction problem, The satisfiability threshold for random linear equations, Belief propagation on the random \(k\)-SAT model, Random hypergraphs and property B, On the constraint length of random \(k\)-CSP, Waiter-client and client-waiter colourability and \(k\)-SAT games, Many hard examples in exact phase transitions, Delaying satisfiability for random 2SAT, The Number of Satisfying Assignments of Random Regulark-SAT Formulas, Selecting Complementary Pairs of Literals