Sharp thresholds and the partition function

ELC International Meeting on Inference, Computation, and Spin Glasses

Coja-Oghlan, Amin^1 ; Reichman, Daniel^2

Goethe University, Mathematics Institute, 10 Robert Mayer St, Frankfurt 60325, Germany^1

Weizmann Institute, Rehovot, Israel^2

关键词: K-CNF formulas;    Partition functions;    Satisfiability;    Satisfying assignments;    Sharp threshold;   

Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/473/1/012015/pdf
DOI  :  10.1088/1742-6596/473/1/012015

来源: IOP

【 摘 要 】

Let Φ be a random k-CNF formula over n variables with clauses and let Z(Φ) be the number of satisfying assignments. Assume that k is sufficiently large and that r ≤ (1 - ok(1))2kln(k)/k, where ok(1)denotes a certain function that tends to 0 as k gets large. We prove that in this case, Φ is satisfiable with probability 1 - O(1/n). Together with a recent result of Abbe and Montanari [arXiv:1006.3786], this implies that for such k,r the limit exists. The existence of this limit is related to the existence of a sharp threshold for satisfiability.