A note on random k-SAT for moderately growing k

MaRDI QIDQ426783zbMATH OpenFDO

Authors Ke Xu, Zongsheng Gao, Jun Liu

Publication date 12 June 2012

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.emis.de/journals/EJC/ojs/index.php/eljc/article/view/v19i1p24

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

k-SATphase transitionsecond moment method

Mathematics Subject Classification ID

Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• Random k-sat: the limiting probability for satisfiability for moderately growing k
• Random k-SAT: A tight threshold for moderately growing k
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))
• Proof of the satisfiability conjecture for large \(k\)

Cited in

(6)

• Random k-sat: the limiting probability for satisfiability for moderately growing k
• On the constraint length of random \(k\)-CSP
• Random k-SAT: A tight threshold for moderately growing k
• Biased random k‐SAT
• Sharp phase transitions for the overlap gap property
• Sharp thresholds for the overlap gap property: Ising p-spin Glass and random k-SAT

This page was built for publication: A note on random \(k\)-SAT for moderately growing \(k\)

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