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

The low-temperature driven or thermally activated motion of several condens ed matter systems is often modeled by the dynamics of interfaces (co-dimens ion-l elastic manifolds) subject to a random potential. Two characteristic quantitative features of the energy landscape of such a many-degree-of-free dom system are the ground-state energy and the magnitude of the energy barr iers between given configurations. While the numerical determination of the former can be accomplished in time polynomial in the system size, it is sh own here that the problem of determining the latter quantity is nondetermin istic polynomial time complete. Exact computation of barriers is therefore (almost certainly) much more difficult than determining the exact ground st ates of interfaces. [S1063-651X(98)14611-1].