The asymptotic k-SAT threshold

Coja-Oghlan, Amin and Panagiotou, Konstantinos (2016): The asymptotic k-SAT threshold. In: Advances in Mathematics, Vol. 288: pp. 985-1068

Abstract

Since the early 20005 physicists have developed an ingenious but non-rigorous formalism called the cavity method to put forward precise conjectures on phase transitions in random problems (Mezard et al., 2002 [37]). The cavity method predicts that the satisfiability threshold in the random k-SAT problem is r(k-SAT) = 2(k) in 2 - 1/2 (1 + ln2) + epsilon(k), with lim(k ->infinity) epsilon(k) = 0 (Mertens et al., 2006 [35]). This paper contains a proof of the conjecture. (C) 2015 ELSEVIER. All rights reserved.

• Item Type: Journal article
• Faculties: Mathematics, Computer Science and Statistics > Mathematics
• Subjects: 500 Science > 510 Mathematics
• ISSN: 0001-8708
• Language: English