Random subcubes as a toy model for constraint satisfaction problems

Simple item page
dc.creatorMora, Thierry
dc.creatorZdeborova, Lenka
dc.date2007-10-19
dc.date2008-01-28
dc.date.accessioned2026-07-07T09:40:15Z
dc.date.available2026-07-07T09:40:15Z
dc.descriptionWe present an exactly solvable random-subcube model inspired by the structure of hard constraint satisfaction and optimization problems. Our model reproduces the structure of the solution space of the random k-satisfiability and k-coloring problems, and undergoes the same phase transitions as these problems. The comparison becomes quantitative in the large-k limit. Distance properties, as well the x-satisfiability threshold, are studied. The model is also generalized to define a continuous energy landscape useful for studying several aspects of glassy dynamics.
dc.description21 pages, 4 figures
dc.identifierhttps://arxiv.org/abs/0710.3804
dc.identifierhttp://arxiv.org/abs/0710.3804
dc.identifierJ. Stat. Phys. 131, n. 6 (2008), 1121-1138
dc.identifierdoi:10.1007/s10955-008-9543-x
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/161426
dc.subjectComputational Complexity
dc.subjectDisordered Systems and Neural Networks
dc.titleRandom subcubes as a toy model for constraint satisfaction problems
dc.typetext

Files

Collections

arXiv