Branching Process approach for 2-SAT thresholds

Details Branching Process approach for 2-SAT thresholds Branching Process approach for 2-SAT thresholds

2008-03-22

arxiv.org/abs/0803.3285v2

Mathematics

Probability

added references, minor modification

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Branching Process approach for 2-SAT thresholds does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Branching Process approach for 2-SAT thresholds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Branching Process approach for 2-SAT thresholds will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-597065