The random K-satisfiability problem: from an analytic solution to an efficient algorithm

Details The random K-satisfiability problem: from an analytic solution to an efficient algorithm The random K-satisfiability problem: from an analytic solution to an efficient algorithm

2002-07-08

arxiv.org/abs/cond-mat/0207194v3

Phys. Rev. E 66 (2002) 056126

Physics

Condensed Matter

Disordered Systems and Neural Networks

38 pages, 13 figures; corrected typos

Scientific paper

10.1103/PhysRevE.66.056126

We study the problem of satisfiability of randomly chosen clauses, each with K Boolean variables. Using the cavity method at zero temperature, we find the phase diagram for the K=3 case. We show the existence of an intermediate phase in the satisfiable region, where the proliferation of metastable states is at the origin of the slowdown of search algorithms. The fundamental order parameter introduced in the cavity method, which consists of surveys of local magnetic fields in the various possible states of the system, can be computed for one given sample. These surveys can be used to invent new types of algorithms for solving hard combinatorial optimizations problems. One such algorithm is shown here for the 3-sat problem, with very good performances.

Affiliated with

Also associated with

No associations

Rating

The random K-satisfiability problem: from an analytic solution to an efficient algorithm 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 random K-satisfiability problem: from an analytic solution to an efficient algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The random K-satisfiability problem: from an analytic solution to an efficient algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-172350