Constraint satisfaction problems with isolated solutions are hard
Constraint satisfaction problems with isolated solutions are hard
复制标题
DOI：
10.1088/1742-5468/2008/12/p12004
复制
发表时间：
2008-12-01
影响因子：
2.4
通讯作者：
Mezard, Marc
中科院分区：
文献类型：
--
作者：
Zdeborova, Lenka;Mezard, Marc
我们研究的相图和算法的硬度的随机“锁定”约束满足问题，并比较他们通常研究的“非锁定”的问题，如布尔公式的可满足性或图着色。锁定问题的特殊性质是解的簇是孤立点。这大大简化了相图的确定，从数学的角度来看，这使得锁定问题特别有吸引力。另一方面，我们的经验表明，这些问题的聚类阶段是非常困难的算法的角度来看：最知名的算法都未能找到解决方案。我们的研究结果表明，容易/困难的过渡（目前已知的算法）在锁定的问题与聚类过渡。因此，这些应被视为真正的硬约束满足问题的新基准。
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.