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

چکیده انگلیسی
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
Journal: Advances in Mathematics - Volume 288, 22 January 2016, Pages 985-1068
نویسندگان
Amin Coja-Oghlan, Konstantinos Panagiotou,