Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems

Simple item page
dc.creatorKrzakala, Florent
dc.creatorZdeborová, Lenka
dc.date2007-11-01
dc.date.accessioned2026-07-07T09:18:08Z
dc.date.available2026-07-07T09:18:08Z
dc.descriptionWe review the understanding of the random constraint satisfaction problems, focusing on the q-coloring of large random graphs, that has been achieved using the cavity method of the physicists. We also discuss the properties of the phase diagram in temperature, the connections with the glass transition phenomenology in physics, and the related algorithmic issues.
dc.description10 pages, Proceedings of the International Workshop on Statistical-Mechanical Informatics 2007, Kyoto (Japan) September 16-19, 2007
dc.identifierhttps://arxiv.org/abs/0711.0110
dc.identifierhttp://arxiv.org/abs/0711.0110
dc.identifier2008 J. Phys.: Conf. Ser. 95 012012
dc.identifierdoi:10.1088/1742-6596/95/1/012012
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/153920
dc.subjectComputational Complexity
dc.subjectStatistical Mechanics
dc.titlePhase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
dc.typetext

Files

Collections

arXiv