Phase Transitions and Critical Phenomena in NP-complete Problems

University Of New Mexico, Albuquerque NM

Investigators

Abstract

0200909 Moore Many search and optimization problems that occur in the real world consist of "constraint satisfaction" tasks where we wish to simultaneously satisfy many 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 than an exponential amount of computational effort. However, this definition of computational complexity focuses on the worst case, not on the typical cases 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. Many people have observed that when the density of constraints passes a critical threshold, these problems undergo a phase transition from solvability to unsolvability. Approaches from physics have already helped us understand this transition. We will prove rigorous upper and lower bounds on the value of this threshold, analyze the performance of heuristics that attempt to solve these problems quickly, and research the effectiveness of the "Replica Trick" of statistical physics in this area.