Zdeborová Lenka, Mézard Marc
Université Paris-Sud, LPTMS, UMR8626, Bât. 100, Université Paris-Sud 91405 Orsay Cedex, France.
Phys Rev Lett. 2008 Aug 15;101(7):078702. doi: 10.1103/PhysRevLett.101.078702.
We introduce and study the random "locked" constraint satisfaction problems. When increasing the density of constraints, they display a broad "clustered" phase in which the space of solutions is divided into many isolated points. While the phase diagram can be found easily, these problems, in their clustered phase, are extremely hard from the algorithmic point of view: the best known algorithms all fail to find solutions. We thus propose new benchmarks of really hard optimization problems and provide insight into the origin of their typical hardness.
我们引入并研究了随机“锁定”约束满足问题。当增加约束密度时，它们会呈现出一个宽泛的“聚类”阶段，在这个阶段中，解空间被划分为许多孤立的点。虽然相图很容易找到，但从算法角度来看，这些问题在其聚类阶段极其困难：所有已知的最佳算法都无法找到解。因此，我们提出了真正困难的优化问题的新基准，并深入了解了它们典型难度的根源。
