Logo Logo
Switch Language to German

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

Full text not available from 'Open Access LMU'.


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.

Actions (login required)

View Item View Item