Title

Computational Complexity of Determining the Barriers to Interface Motion in Random Systems

Author(s)/Creator(s)

Alan Middleton, Syracuse UniversityFollow

Document Type

Article

Date

2-14-1999

Language

English

Disciplines

Physics

Description/Abstract

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 NP-complete. Exact computation of barriers is therefore (almost certainly) much more difficult than determining the exact ground states of interfaces.

Additional Information

8 pages, figures included, to appear in Phys. Rev. E More information at http://arxiv.org/abs/cond-mat/9902203

Recommended Citation

Middleton, Alan, "Computational Complexity of Determining the Barriers to Interface Motion in Random Systems" (1999). Physics - All Scholarship. 198.
https://surface.syr.edu/phy/198

Source

Harvested from Arxiv.org

Creative Commons License

This work is licensed under a Creative Commons Attribution 3.0 License.