PerspectiveMathematics

Being Glassy Without Being Hard to Solve

+ See all 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

Summary

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.