The asymptotic k-SAT threshold

Coja-Oghlan, Amin und Panagiotou, Konstantinos (2016): The asymptotic k-SAT threshold. In: Advances in Mathematics, Bd. 288: S. 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.

• Dokumententyp: Zeitschriftenartikel
• Fakultät: Mathematik, Informatik und Statistik > Mathematik
• Themengebiete: 500 Naturwissenschaften und Mathematik > 510 Mathematik
• ISSN: 0001-8708
• Sprache: Englisch