Achlioptas Dimitris, Naor Assaf, Peres Yuval
Microsoft Research, One Microsoft Way, Redmond, Washington 98052, USA.
Nature. 2005 Jun 9;435(7043):759-64. doi: 10.1038/nature03602.
It is widely believed that for many optimization problems, no algorithm is substantially more efficient than exhaustive search. This means that finding optimal solutions for many practical problems is completely beyond any current or projected computational capacity. To understand the origin of this extreme 'hardness', computer scientists, mathematicians and physicists have been investigating for two decades a connection between computational complexity and phase transitions in random instances of constraint satisfaction problems. Here we present a mathematically rigorous method for locating such phase transitions. Our method works by analysing the distribution of distances between pairs of solutions as constraints are added. By identifying critical behaviour in the evolution of this distribution, we can pinpoint the threshold location for a number of problems, including the two most-studied ones: random k-SAT and random graph colouring. Our results prove that the heuristic predictions of statistical physics in this context are essentially correct. Moreover, we establish that random instances of constraint satisfaction problems have solutions well beyond the reach of any analysed algorithm.
人们普遍认为，对于许多优化问题，没有哪种算法比穷举搜索更高效。这意味着为许多实际问题找到最优解完全超出了当前或预计的计算能力。为了理解这种极端“难度”的根源，计算机科学家、数学家和物理学家二十年来一直在研究约束满足问题随机实例中的计算复杂性与相变之间的联系。在此，我们提出一种用于定位此类相变的数学严谨方法。我们的方法通过分析随着约束增加，解对之间距离的分布来起作用。通过识别这种分布演变中的临界行为，我们可以确定许多问题的阈值位置，包括研究最多的两个问题：随机k - SAT问题和随机图着色问题。我们的结果证明，在此背景下统计物理学的启发式预测基本正确。此外，我们确定约束满足问题的随机实例具有任何已分析算法都无法企及的解。
