Computational complexity of the landscape I

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 (39)

• de Sitter Vacua in String Theory
• Hierarchies from Fluxes in String Compactifications
• Quantization of Four-form Fluxes and Dynamical Neutralization of the Cosmological Constant
• N=2 Extremal Black Holes
• M Theory, Orientifolds and G-Flux
• The statistics of string/M theory vacua
• The Anthropic Landscape of String Theory
• Large and infinite extra dimensions
• Distributions of flux vacua
• Quantum Computation by Adiabatic Evolution
• Building a Better Racetrack
• Inflation and Eternal Inflation
• The anthropic principle and the mass scale of the Standard Model
• Exact solutions for supersymmetric stationary black hole composites
• Calabi-Yau fourfolds for M- and F-Theory compactifications
• Distributions of nonsupersymmetric flux vacua
• Simulating lattice gauge theories on a quantum computer
• The Scaling of the No Scale Potential and de Sitter Model Building
• The Statistics of Supersymmetric D-brane Models
• Quantum information and physics: some future directions
• Basic results in Vacuum Statistics
• On the Explicit Construction and Statistics of Calabi-Yau Flux Vacua
• Supersymmetry Breaking in the Anthropic Landscape
• Statistical analysis of the supersymmetry breaking scale
• How far are we from the quantum theory of gravity?
• Time-Varying alpha and Particle Physics
• Heretics of the False Vacuum: Gravitational Effects On and Of Vacuum Decay 2
• Irrational Axions as a Solution of The Strong CP Problem in an Eternal Universe
• Landskepticism: or Why Effective Potentials Don't Count String Models
• Introduction to Cosmic F- and D-Strings
• A Review of Distributions on the String Landscape
• Some Thoughts on the Quantum Theory of Stable de Sitter Space
• Noncomputability Arising In Dynamical Triangulation Model Of Four-Dimensional Quantum Gravity
• Finiteness of volume of moduli spaces
• Regulating Eternal Inflation
• The Physics of Extra Dimensions
• Describing codimension two defects
• How to Make the Quantum Adiabatic Algorithm Fail
• Minimax Games, Spin Glasses and the Polynomial-Time Hierarchy of Complexity Classes

Cited by in corpus (91)

• Four-dimensional String Compactifications with D-Branes, Orientifolds and Fluxes
• The QCD Axion and Moduli Stabilisation
• Supersymmetric Standard Model Spectra from RCFT orientifolds
• Quantum Computation vs. Firewalls
• 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
• Machine Learning in the String Landscape
• The landscape of intersecting brane models
• Higgs Bundles and UV Completion in F-Theory
• Life at the Interface of Particle Physics and String Theory
• Moduli Stabilization in Non-Geometric Backgrounds
• Branes with Brains: Exploring String Vacua with Deep Reinforcement Learning
• Tuning and Backreaction in F-term Axion Monodromy Inflation
• On Algorithmic Universality in F-theory Compactifications
• Genetic Algorithms and the Search for Viable String Vacua
• Supersymmetry versus Gauge Symmetry on the Heterotic Landscape
• Searching the Landscape of Flux Vacua with Genetic Algorithms
• Probabilities in the landscape: The decay of nearly flat space
• Landscape Predictions from Cosmological Vacuum Selection
• Computational Complexity of Vacua and Near-Vacua in Field and String Theory
• Moduli Stabilization in Asymptotic Flux Compactifications
• Vacuum Selection from Cosmology on Networks of String Geometries
• A geometric solution to the coincidence problem, and the size of the landscape as the origin of hierarchy
• The Calabi-Yau Landscape: from Geometry, to Physics, to Machine-Learning
• TASI lectures on complex structures
• Machine learning for complete intersection Calabi-Yau manifolds: a methodological study
• Fighting the Floating Correlations: Expectations and Complications in Extracting Statistical Correlations from the String Theory Landscape
• Computational complexity of the landscape II - Cosmological considerations
• The string landscape and low energy supersymmetry
• Estimating Calabi-Yau Hypersurface and Triangulation Counts with Equation Learners
• The Self-Organized Critical Multiverse
• Vacuum Structure and the Arrow of Time
• Explore and Exploit with Heterotic Line Bundle Models
• On the computation of non-perturbative effective potentials in the string theory landscape -- IIB/F-theory perspective
• Classical transitions with the topological number changing in the early Universe
• Fast optimization algorithms and the cosmological constant
• On de Sitter Spacetime and String Theory
• Fluxes, Vacua, and Tadpoles meet Landau-Ginzburg and Fermat
• Statistical Predictions in String Theory and Deep Generative Models
• Accessibility Measure for Eternal Inflation: Dynamical Criticality and Higgs Metastability
• Search Optimization, Funnel Topography, and Dynamical Criticality on the String Landscape
• Revealing systematics in phenomenologically viable flux vacua with reinforcement learning
• Extremal Black Holes in Supergravity
• The Cost of Seven-brane Gauge Symmetry in a Quadrillion F-theory Compactifications
• Artificial Neural Network in Cosmic Landscape
• Correlation Classes on the Landscape: To What Extent is String Theory Predictive?
• Gauge sector statistics of intersecting D-brane models
• Deep multi-task mining Calabi-Yau four-folds
• Inflation Expels Runaways
• Deforming, revolving and resolving - New paths in the string theory landscape
• Rigour and Rigidity: Systematics on particle physics D6-brane models on Z(2)xZ(6)
• An Entropy-Weighted Sum over Non-Perturbative Vacua
• Freedom and Constraints in the K3 Landscape
• The Dark Universe after Reheating in String Inflation
• Kahler Moduli Stabilization and the Propagation of Decidability
• Early-Time Measure in Eternal Inflation
• 6D (1,1) Gauged Supergravities from Orientifold Compactifications
• Higher Spin de Sitter Hilbert Space
• A landscape for the cosmological constant and the Higgs mass
• Why trust a theory? Some further remarks (part 1)
• Ising Machines for Diophantine Problems in Physics
• Holomorphic Couplings In Non-Perturbative String Compactifications
• On finiteness of Type IIB compactifications: Magnetized branes on elliptic Calabi-Yau threefolds
• No-Bang Quantum State of the Cosmos
• Constraints on Standard Model Constructions in F-theory
• Deep learning complete intersection Calabi-Yau manifolds
• Extremal Bundles on Calabi-Yau Threefolds
• Eternal inflation and localization on the landscape
• A Local Wheeler-DeWitt Measure for the String Landscape
• A Cosmological Constant That is Too Small
• Universes as Big Data
• Can biological quantum networks solve NP-hard problems?
• Dynamics of genetic code evolution: The emergence of universality
• The grainy multiverse
• Statistics in the Landscape of Intersecting Brane Models
• Bounding the Heat Trace of a Calabi-Yau Manifold
• Topological Data Analysis for the String Landscape
• Cosmological Constant Seesaw in String/M-Theory
• Seeking a Game in which the standard model Group shall Win
• Computability and Complexity of Unconventional Computing Devices
• Polynomial Roots and Calabi-Yau Geometries
• High Performance Algorithms for Quantum Gravity and Cosmology
• Entropy, heat, and Gödel incompleteness
• Turing's Landscape: decidability, computability and complexity in string theory
• Probing the Structure of String Theory Vacua with Genetic Algorithms and Reinforcement Learning
• Ranks of gauge groups and an NP-complete problem on the Landscape
• A Computational Anthropic Principle: Where is the Hardest Problem in the Multiverse?
• Vacuum Branching, Dark Energy, Dark Matter
• Notes on the firewall paradox, complexity, and quantum theory