Computational complexity of the landscape I
arXiv:hep-th/0602072 · doi:10.1016/j.aop.2006.07.013
Abstract
We study the computational complexity of the physical problem of finding vacua of string theory which agree with data, such as the cosmological constant, and show that such problems are typically NP hard. In particular, we prove that in the Bousso-Polchinski model, the problem is NP complete. We discuss the issues this raises and the possibility that, even if we were to find compelling evidence that some vacuum of string theory describes our universe, we might never be able to find that vacuum explicitly. In a companion paper, we apply this point of view to the question of how early cosmology might select a vacuum.
JHEP3 Latex, 53 pp, 2 .eps figures
References in corpus (8)
- The Anthropic Landscape of String Theory
- Statistical analysis of the supersymmetry breaking scale
- How far are we from the quantum theory of gravity?
- Heretics of the False Vacuum: Gravitational Effects On and Of Vacuum Decay 2
- Landskepticism: or Why Effective Potentials Don't Count String Models
- Introduction to Cosmic F- and D-Strings
- Some Thoughts on the Quantum Theory of Stable de Sitter Space
- Finiteness of volume of moduli spaces
Cited by in corpus (20)
- Four-dimensional String Compactifications with D-Branes, Orientifolds and Fluxes
- Les Houches Lectures on Constructing String Vacua
- Orientifolds, hypercharge embeddings and the Standard Model
- The Cosmological Constant and the String Landscape
- Statistics on the Heterotic Landscape: Gauge Groups and Cosmological Constants of Four-Dimensional Heterotic Strings
- Higgs Bundles and UV Completion in F-Theory
- Moduli Stabilization in Non-Geometric Backgrounds
- Supersymmetry versus Gauge Symmetry on the Heterotic Landscape
- Probabilities in the landscape: The decay of nearly flat space
- Landscape Predictions from Cosmological Vacuum Selection
- Fighting the Floating Correlations: Expectations and Complications in Extracting Statistical Correlations from the String Theory Landscape
- Extremal Black Holes in Supergravity
- Gauge sector statistics of intersecting D-brane models
- Deforming, revolving and resolving - New paths in the string theory landscape
- An Entropy-Weighted Sum over Non-Perturbative Vacua
- No-Bang Quantum State of the Cosmos
- Eternal inflation and localization on the landscape
- Statistics in the Landscape of Intersecting Brane Models
- Cosmological Constant Seesaw in String/M-Theory
- Turing's Landscape: decidability, computability and complexity in string theory