  We demonstrate that the problems of finding stable or metastable vacua in a
low energy effective field theory requires solving nested NP-hard and
co-NP-hard problems, while the problem of finding near-vacua is in P. Multiple
problems relevant for computing effective potential contributions from string
theory are shown to be instances of NP-hard problems. If P $\neq$ NP, the
hardness of finding string vacua is exponential in the number of scalar fields.
Cosmological implications, including for rolling solutions, are discussed in
light of a recently proposed measure.

High Energy Physics - Theory