TY - JOUR

T1 - Branching process approach for 2-sat thresholds

AU - Mossel, Elchanan

AU - Sen, Arnab

PY - 2010/9

Y1 - 2010/9

N2 - It is well known that, as n tends to∞, the probability of satisfiability for a random 2-SAT formula on n variables, where each clause occurs independently with probability α/2n, exhibits a sharp threshold at α = 1. We study a more general 2-SAT model in which each clause occurs independently but with probability αi/2n, where i ε {0, 1, 2} is the number of positive literals in that clause. We generalize the branching process arguments used byVerhoeven (1999) to determine the satisfiability threshold for this model in terms of the maximum eigenvalue of the branching matrix.

AB - It is well known that, as n tends to∞, the probability of satisfiability for a random 2-SAT formula on n variables, where each clause occurs independently with probability α/2n, exhibits a sharp threshold at α = 1. We study a more general 2-SAT model in which each clause occurs independently but with probability αi/2n, where i ε {0, 1, 2} is the number of positive literals in that clause. We generalize the branching process arguments used byVerhoeven (1999) to determine the satisfiability threshold for this model in terms of the maximum eigenvalue of the branching matrix.

KW - 2-SAT

KW - Phase transition

KW - Satisfiability

KW - Two-type branching process

UR - http://www.scopus.com/inward/record.url?scp=80053990360&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80053990360&partnerID=8YFLogxK

U2 - 10.1239/jap/1285335410

DO - 10.1239/jap/1285335410

M3 - Article

AN - SCOPUS:80053990360

SN - 0021-9002

VL - 47

SP - 796

EP - 810

JO - Journal of Applied Probability

JF - Journal of Applied Probability

IS - 3

ER -