A lower bound for the 4-satisfiability threshold

DOI10.1515/DMA.2007.025MaRDI QIDQ5439053zbMATH OpenOpenAlexFDO

Authors F. Yu. Vorob'ev

Publication date 8 February 2008

Published in Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4213/dm25

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Recommendations

• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))
• On the Lower Bounds of Random Max 3 and 4-SAT
• On the lower bounds of random Max 3 and 4-SAT
• On the satisfiability threshold of formulas with three literals per clause

Cites work

• Sharp thresholds of graph properties, and the k-sat problem

Cited in

(4)

• On the lower bounds of random Max 3 and 4-SAT
• On the Lower Bounds of Random Max 3 and 4-SAT
• On the lower bounds of \((1, 0)\)-super solutions for random \(k\)-SAT
• Results related to threshold phenomena research in satisfiability: Lower bounds

This page was built for publication: A lower bound for the 4-satisfiability threshold

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