The unsatisfiability threshold revisited

DOI10.1016/j.dam.2005.10.017zbMath1149.90125OpenAlexW2090680193MaRDI 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

complexityphase transitionprobabilistic analysissatisfiability

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items (4)

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

Uses Software

• Maple

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: The unsatisfiability threshold revisited