12-09

Phase Transitions in Hard Optimization Problems

ABSTRACT: Many NP-complete problems are easy for random inputs. For example, in a random graph where each edge is present with probability 1/2 one can find a Hamiltonian cycle in linear time, almost surely. On the other hand, random instances of satisfiability and graph coloring appear to be hard. Moreover, each problem appears to be hardest near its "threshold", a constraint density around which the probability of solubility drops rapidly from near 1 to near 0. Locating these two thresholds and understanding the behavior of algorithms near them is an active topic of research in artificial intelligence, combinatorics, probability, theoretical computer science, and statistical physics.

We study how the structure of the set of solutions evolves in each of these two problems as constraints are added. This allows us to determine the location of the threshold for both random satisfiability and random graph colorability up to second order terms. To do this we prove that for a large class of random constraint satisfaction problems the second moment of the number of solutions is captured by an "entropy-energy" tradeoff. Critical values of this tradeoff correspond to points where the structure of the space of solutions undergoes dramatic change. By identifying these critical points, we not only get to locate thresholds but we also gain rigorous insight on why algorithms have a hard time near them.

Based on joint works with Assaf Naor (Microsoft) and Yuval Peres (Berkeley).