Fast optimization algorithms and the cosmological constant
Ning Bao, Raphael Bousso, Stephen P. Jordan, Brad Lackey · Physical review. D/Physical review. D. · 2017
Denef and Douglas have observed that in certain landscape models the problem of finding small values of the cosmological constant is a large instance of a problem that is hard for the complexity class NP (Nondeterministic Polynomial-time). The number of elementary operations (quantum gates) needed to solve this problem by brute force search exceeds the estimated computational capacity of the observable Universe. Here we describe a way out of this puzzling circumstance: despite being NP-hard, the problem of finding a small cosmological constant can be attacked by more sophisticated algorithms whose performance vastly exceeds brute force search. In fact, in some parameter regimes the average-case complexity is polynomial. We demonstrate this by explicitly finding a cosmological constant of order ${10}^{\ensuremath{-}120}$ in a randomly generated $1{0}^{9}$-dimensional Arkani-Hamed--Dimopoulos--Kachru landscape.