On the phase transitions of \((k, q)\)-SAT

DOI10.1007/S10255-016-0591-8zbMath1359.05134OpenAlexW2514057803MaRDI QIDQ517195

Ke Xu, Jun Liu, Zong Sheng Gao

Publication date: 23 March 2017

Published in: Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10255-016-0591-8

zbMATH Keywords

phase transitionconstraint satisfactionsecond moment method

Mathematics Subject Classification ID

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

Cites Work

• A general model and thresholds for random constraint satisfaction problems
• On the phase transitions of random \(k\)-constraint satisfaction problems
• A sharp threshold for a random constraint satisfaction problem
• Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Unnamed Item

This page was built for publication: On the phase transitions of \((k, q)\)-SAT