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

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.

8 pages, figures included, to appear in Phys. Rev. E

References in corpus (1)

• Ground-State Roughness of the Disordered Substrate and Flux Line in d=2

Cited by in corpus (8)

• Dynamics below the depinning threshold
• Critical slowing down in polynomial time algorithms
• Determining Energy Barriers by Iterated Optimization: The Two-Dimensional Ising Spin Glass
• Equilibrium of disordered systems : constructing the appropriate valleys in each sample via strong disorder renormalization in configuration space
• Non-equilibrium dynamics of polymers and interfaces in random media : conjecture $\psi =d_s/2$ for the barrier exponent
• Driven interfaces in random media at finite temperature : is there an anomalous zero-velocity phase at small external force ?
• Non-equilibrium dynamics of finite-dimensional disordered systems : RG flow towards an "infinite disorder" fixed point at large times
• Energy barriers in spin glasses