Phase Transitions and Critical Phenomena in NP-complete Problems

0200909移动现实世界中出现的许多搜索和优化问题都是由“约束满足”任务组成的，我们希望同时满足许多需求。这些问题发生在调度、制造、编译器和许多其他环境中。这些问题中的许多都是“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.