Constraint satisfaction problems with isolated solutions are hard

Details Constraint satisfaction problems with isolated solutions are hard Constraint satisfaction problems with isolated solutions are hard

2008-10-08

arxiv.org/abs/0810.1499v2

J. Stat. Mech. (2008) P12004

Physics

Condensed Matter

Disordered Systems and Neural Networks

19 pages, 12 figures

Scientific paper

10.1088/1742-5468/2008/12/P12004

We study the phase diagram and the algorithmic hardness of the random `locked' constraint satisfaction problems, and compare them to the commonly studied 'non-locked' problems like satisfiability of boolean formulas or graph coloring. The special property of the locked problems is that clusters of solutions are isolated points. This simplifies significantly the determination of the phase diagram, which makes the locked problems particularly appealing from the mathematical point of view. On the other hand we show empirically that the clustered phase of these problems is extremely hard from the algorithmic point of view: the best known algorithms all fail to find solutions. Our results suggest that the easy/hard transition (for currently known algorithms) in the locked problems coincides with the clustering transition. These should thus be regarded as new benchmarks of really hard constraint satisfaction problems.

Affiliated with

Also associated with

No associations

Rating

Constraint satisfaction problems with isolated solutions are hard 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 Constraint satisfaction problems with isolated solutions are hard, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constraint satisfaction problems with isolated solutions are hard will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-30631