期刊
RANDOM STRUCTURES & ALGORITHMS
卷 28, 期 3, 页码 340-373出版社
WILEY-BLACKWELL
DOI: 10.1002/rsa.20090
关键词
satisfiability; K-SAT; threshold phenomenon; phase transition; cavity approach; survey propagation; average case complexity
Using the cavity equations of Mezard, Parisi, and Zecchina [Science 297 (2002), 812; Mezard and Zecchina, Phys Rev E 66 (2002), 056126] we derive the various threshold values for the number of clauses per variable of the random K-satisfiability problem, generalizing the previous results to K >= 4. We also give an analytic solution of the equations, and some closed expressions for these thresholds, in an expansion around large K. The stability of the solution is also computed. For any K, the satisfiability threshold is found to be in the stable region of the solution, which adds further credit to the conjecture that this computation gives the exact satisfiability threshold. (c) 2005 Wiley Periodicals, Inc.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据