The Asymptotic Order of the k-SAT Threshold

Details The Asymptotic Order of the k-SAT Threshold The Asymptotic Order of the k-SAT Threshold

2002-09-26

arxiv.org/abs/cond-mat/0209622v1

Physics

Condensed Matter

Statistical Mechanics

Conference version to appear in FOCS (Foundations of Computer Science) 2002

Scientific paper

Form a random k-SAT formula on n variables by selecting uniformly and independently m=rn clauses out of all 2^k (n choose k) possible k-clauses. The Satisfiability Threshold Conjecture asserts that for each k there exists a constant r_k such that, as n tends to infinity, the probability that the formula is satisfiable tends to 1 if r < r_k and to 0 if r > r_k. It has long been known that 2^k / k < r_k < 2^k. We prove that r_k > 2^{k-1} \ln 2 - d_k, where d_k \to (1+\ln 2)/2. Our proof also allows a blurry glimpse of the ``geometry'' of the set of satisfying truth assignments, and a nearly exact location of the threshold for Not-All-Equal (NAE) k-SAT.

Affiliated with

Also associated with

No associations

Rating

The Asymptotic Order of the k-SAT Threshold 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 The Asymptotic Order of the k-SAT Threshold, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Asymptotic Order of the k-SAT Threshold will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-523486