Average-case analysis of computational complexity presents strong affinities with the study of disordered systems in statistical mechanics. 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 detailed and 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 condensates 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 consequences of our results.

LPTMS, Orsay