Phase Transitions and Critical Phenomena in NP-complete Problems

0200909摩尔许多搜索和优化问题，发生在真实的世界constitof“约束满足”的任务，我们希望同时满足许多需求。 这些问题发生在调度、制造、编译器和许多其他环境中。这些问题中的许多是“NP完全”的，这意味着它们可能无法用少于指数级的计算工作量来解决。 然而，这种计算复杂性的定义关注的是最坏的情况，而不是我们在真实的世界中可能发现的典型情况。作为最坏情况和真实世界问题之间的数学桥梁，我们将考虑NP完全问题的随机或平均情况。 许多人已经观察到，当约束密度超过临界阈值时，这些问题经历了从可解到不可解的相变。物理学的方法已经帮助我们理解了这种转变。 我们将证明严格的上限和下限的值，这个阈值，分析性能的统计学，试图解决这些问题迅速，并研究在这方面的统计物理学的“欺骗伎俩”的有效性。

0200909 MooreMany search and optimization problems that occur in the real world consistof "constraint satisfaction" tasks where we wish to simultaneously satisfymany demands. These problems occur in scheduling, manufacturing,compilers, and many other contexts. Many of these problems are"NP-complete," meaning that they can probably not be solved with less thanan exponential amount of computational effort. However, this definitionof computational complexity focuses on the worst case, not on the typicalcases we might find in the real world.As a mathematical bridge between the worst case and real-world problems,we will consider random, or average, cases of NP-complete problems. Manypeople have observed that when the density of constraints passes acritical threshold, these problems undergo a phase transition fromsolvability to unsolvability. Approaches from physics have already helpedus understand this transition. We will prove rigorous upper and lowerbounds on the value of this threshold, analyze the performance ofheuristics that attempt to solve these problems quickly, and research theeffectiveness of the "Replica Trick" of statistical physics in this area.