Phase transitions in constraint satisfaction problems
by
Lenka Zdeborova(U Paris-Sud)
→
Europe/Stockholm
Description
Average-case analysis of computational complexity presents strong affinities with the study of disordered systems in statistical mechanics. As an example we consider the problem of coloring a large random graph with a given number of colors such that no adjacent vertexes have the same color. Using the cavity method, we present a systematic study of the phase space of the solutions for different connectivities and numbers of colors. We show that, for fixed number of colors and as the connectivity increases, the set of solutions undergoes different phase transitions similar to those happening in the mean field theory of glasses. First, the phase space decomposes into an exponential number of pure states, and subsequently condenses over the largest such states. Another transition takes place when a finite fraction of frozen variables appears inside almost all the dominant pure states. Eventually a connectivity is reached beyond which no solutions are available. Finally, we discuss the algorithmic perspectives of our results, in particular the role of variable freezing.
