The unsatisfiability threshold revisited

DOI10.1016/j.dam.2005.10.017zbMath1149.90125MaRDI QIDQ2643297

Michele Zito, Lefteris M. Kirousis, Yannis C. Stamatiou, Malvina G. Vamvakari, Alexis C. Kaporis

Publication date: 23 August 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.10.017

zbMATH Keywords

complexity; phase transition; probabilistic analysis; satisfiability

Mathematics Subject Classification ID

90C27: Combinatorial optimization

90B80: Discrete location and assignment

Related Items

Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random k-SAT, Estimating satisfiability, On the satisfiability threshold and clustering of solutions of random 3-SAT formulas, Super solutions of random \((3 + p)\)-SAT

Uses Software

• Maple

Cites Work

• On the Lambert \(w\) function
• Approximating the unsatisfiability threshold of random formulas
• Sharp thresholds of graph properties, and the $k$-sat problem
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• Bounding the unsatisfiability threshold of random 3-SAT
• Tail bounds for occupancy and the satisfiability threshold conjecture
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item