A note on random \(k\)-SAT for moderately growing \(k\)

zbMath1288.68185MaRDI QIDQ426783

Ke Xu, Jun Liu, Zong Sheng Gao

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

zbMATH Keywords

phase transition; second moment method; k-SAT

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

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

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Related Items

On the constraint length of random \(k\)-CSP