Being Glassy Without Being Hard to Solve

See allHide authors and affiliations

Science  17 Dec 2010:
Vol. 330, Issue 6011, pp. 1639-1640
DOI: 10.1126/science.1189804

You are currently viewing the summary.

View Full Text

Log in to view the full text

Log in through your institution

Log in through your institution


The statistical mechanics that describes collective phenomena in disordered systems and solutions to large search problems have important mathematical connections. One of the models that describes disordered materials, the diluted p-spin model, is strongly related to the random XORSAT problem, a problem of finding variables that simultaneously satisfy a large number of logical constraints (1). This relation has provided insight into how small changes in a model can modify its computational difficulty.