1。引入统计力学思想和工具在八十年代中期发起的随机优化问题[1]的应用，这是由于发现在约束满意度问题（CSP）的第五年前的相变的重新兴趣所带来的。brie ploge，一个人想决定是否在一组变量（至少）解决一个解决方案上是否会随机绘制的一组约束。当变量的数量在每个变量的约束时以固定比率α的固定比率α，答案突然从（几乎可以肯定的是）是的，是否，当比率越过一些临界值αs时。统计物理研究指出，在YES区域中存在另一种相变[2，3]。一组解决方案从以某种比例αd <αs的比例连接到断开的簇的集合，这是一种在均值式旋转玻璃理论中识别的副本对称性破坏过渡的优化术语的翻译。预计这种聚类过渡可能会产生动态后果。作为副本对称性打破信号的遗传性丧失，采样算法（例如蒙特卡洛程序）在该过渡时遇到问题。在[4]中，对于k -xorsat模型的情况，对MC方案的放缓进行了定量研究，其中约束仅是k布尔变量的线性方程（Modulo 2）（有关简介，请参见[5]和其中的参考文献）。目前的论文是谦虚的然而，发现解决方案原则上应该比抽样容易，并且分辨率算法的性能与表征解决方案空间的静态相变的性质的确切性质远非显而易见[6]。