کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6425574 1633800 2016 84 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The asymptotic k-SAT threshold
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات (عمومی)
پیش نمایش صفحه اول مقاله
The asymptotic k-SAT threshold
چکیده انگلیسی

Since the early 2000s physicists have developed an ingenious but non-rigorous formalism called the cavity method to put forward precise conjectures on phase transitions in random problems (Mézard et al., 2002 [37]). The cavity method predicts that the satisfiability threshold in the random k-SAT problem is rk-SAT=2kln⁡2−12(1+ln⁡2)+εk, with limk→∞⁡εk=0 (Mertens et al., 2006 [35]). This paper contains a proof of the conjecture.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Advances in Mathematics - Volume 288, 22 January 2016, Pages 985-1068
نویسندگان
, ,