Simplest random K-satisfiability problem

Details Simplest random K-satisfiability problem Simplest random K-satisfiability problem

2000-11-10

arxiv.org/abs/cond-mat/0011181v2

Phys. Rev. E 63, 026702 (2001)

Physics

Condensed Matter

Disordered Systems and Neural Networks

14 pages, 5 figures, to appear in Phys. Rev. E (Feb 2001). v2: minor errors and references corrected

Scientific paper

10.1103/PhysRevE.63.026702

We study a simple and exactly solvable model for the generation of random satisfiability problems. These consist of $\gamma N$ random boolean constraints which are to be satisfied simultaneously by $N$ logical variables. In statistical-mechanics language, the considered model can be seen as a diluted p-spin model at zero temperature. While such problems become extraordinarily hard to solve by local search methods in a large region of the parameter space, still at least one solution may be superimposed by construction. The statistical properties of the model can be studied exactly by the replica method and each single instance can be analyzed in polynomial time by a simple global solution method. The geometrical/topological structures responsible for dynamic and static phase transitions as well as for the onset of computational complexity in local search method are thoroughly analyzed. Numerical analysis on very large samples allows for a precise characterization of the critical scaling behaviour.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-654751