Paper Info
Title
Constraint satisfaction problems with isolated solutions are hard
Abstract
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 formulae 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.
Year
DOI
Venue
2008
10.1088/1742-5468/2008/12/P12004
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT
Keywords
DocType
Volume
analysis of algorithms,message-passing algorithms,random graphs,networks,typical-case computational complexity
Journal
abs/0810.1
Issue
ISSN
Citations 
12
1742-5468
14
PageRank 
References 
Authors
1.23
4
2
Name
Order
Citations
PageRank
Lenka Zdeborová1119078.62
Marc Mézard259039.09