Phase Transitions and Critical Phenomena in NP-complete Problems

NP 完全问题中的相变和临界现象

• 批准号: 0200909
• 负责人: Cristopher Moore
• 金额: $ 16.6万
• 依托单位: University of New Mexico
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-08-15 至 2006-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0200909&HistoricalAwards=false
• 关键词: Phase; Transitions; Critical; Phenomena; 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.

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