Computational complexity of determining the barriers to interface motion in random systems

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


The low-temperature driven or thermally activated motion of several condensed matter systems is often modeled by the dynamics of interfaces (co-dimension-1 elastic manifolds) subject to a random potential. Two characteristic quantitative features of the energy landscape of such a many-degree-of-freedom system are the ground-state energy and the magnitude of the energy barriers between given configurations. While the numerical determination of the former can be accomplished in time polynomial in the system size, it is shown here that the problem of determining the latter quantity is nondeterministic polynomial time complete. Exact computation of barriers is therefore (almost certainly) much more difficult than determining the exact ground states of interfaces.

Original languageEnglish (US)
Pages (from-to)2571-2577
Number of pages7
JournalPhysical Review E - Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics
Issue number3
StatePublished - 1999

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Statistics and Probability
  • Condensed Matter Physics


Dive into the research topics of 'Computational complexity of determining the barriers to interface motion in random systems'. Together they form a unique fingerprint.

Cite this