Threshold values of Random K-SAT from the cavity method

Details Threshold values of Random K-SAT from the cavity method Threshold values of Random K-SAT from the cavity method

2003-09-12

arxiv.org/abs/cs/0309020v2

Computer Science

Computational Complexity

38 pages; extended explanations and derivations; this version is going to appear in Random Structures & Algorithms

Scientific paper

Using the cavity equations of \cite{mezard:parisi:zecchina:02,mezard:zecchina:02}, 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 \ge 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.

Affiliated with

Also associated with

No associations

Rating

Threshold values of Random K-SAT from the cavity method 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 Threshold values of Random K-SAT from the cavity method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Threshold values of Random K-SAT from the cavity method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-230340