Computational complexity of the landscape. I.

DOI10.1016/J.AOP.2006.07.013zbMATH Open1113.83007arXivhep-th/0602072OpenAlexW1939025161WikidataQ56852349 ScholiaQ56852349MaRDI QIDQ877685FDOQ877685

Michael R. Douglas, Frederik Denef

Publication date: 3 May 2007

Published in: Annals of Physics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/hep-th/0602072

Recommendations

• Computational complexity of the landscape. II: Cosmological considerations
• Numerical polynomial homotopy continuation method and string vacua
• On the computation of non-perturbative effective potentials in the string theory landscape -- IIB/F-theory perspective --
• P/NP , and the quantum field computer
• Publication:4939149

Mathematics Subject Classification ID

String and superstring theories; other extended objects (e.g., branes) in quantum field theory (81T30) Einstein's equations (general structure, canonical formalism, Cauchy problems) (83C05) String and superstring theories in gravitational theory (83E30)

Cites Work

• Optimization by Simulated Annealing
• Title not available (Why is that?)
• Simulation of topological field theories by quantum computers
• Title not available (Why is that?)
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computational Complexity
• Factoring polynomials with rational coefficients
• The fundamental constants and their variation: observational and theoretical status
• Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation
• Title not available (Why is that?)
• The cosmological constant problem
• Calabi-Yau four-folds for \(M\)- and \(F\)-theory compactifications
• PRIMES is in P
• De Sitter vacua in string theory
• Saltatory relaxation of the cosmological constant
• The statistics of supersymmetric D-brane models
• Computational complexity of the landscape. I.
• BPP and the polynomial hierarchy
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Fixing all moduli in a simple F-theory compactification
• Computers, Rigidity, and Moduli
• Critical points and supersymmetric vacua, III: String/M models
• Threshold Computation and Cryptographic Security
• HOW TO MAKE THE QUANTUM ADIABATIC ALGORITHM FAIL
• Finding the lowest free energy conformation of a protein is an NP-hard problem: Proof and implications
• The NP-completeness column
• Classical physics and the Church--Turing Thesis
• Noncomputability arising in dynamical triangulation model of four- dimensional quantum gravity
• Progress in quantum algorithms
• The importance of the P versus NP question

Cited In (40)

• Higher spin de Sitter Hilbert space
• Searching the landscape of flux vacua with genetic algorithms
• Branes with brains: exploring string vacua with deep reinforcement learning
• On finiteness of type IIB compactifications: magnetized branes on elliptic Calabi-Yau threefolds
• Fluxes, vacua, and tadpoles meet Landau-Ginzburg and Fermat
• Quantum computation vs. firewalls
• Topological data analysis for the string landscape
• Quantum master equation for the vacuum decay dynamics
• Computational complexity of the landscape. I.
• Orientifolds, hypercharge embeddings and the standard model
• Early-time measure in eternal inflation
• Inflation expels runaways
• Extremal bundles on Calabi-Yau threefolds
• Neural network learning and quantum gravity
• Finiteness theorems and counting conjectures for the flux landscape
• Bounding the heat trace of a Calabi-Yau manifold
• Proton decay, Yukawa couplings and underlying gauge symmetry in string theory
• Higgs bundles and UV completion in \(F\)-theory
• Tuning and backreaction in F-term axion monodromy inflation
• Rigour and rigidity: Systematics on particle physics D6-brane models on \(\mathbb{Z}_{2} \times \mathbb{Z}_{6}\)
• Polynomial roots and Calabi-Yau geometries
• Ising Machines for Diophantine Problems in Physics
• 6D (1,1) gauged supergravities from orientifold compactifications
• Moduli stabilization in non-geometric backgrounds
• Explore and Exploit with Heterotic Line Bundle Models
• Algorithmically solving the tadpole problem
• On the computation of non-perturbative effective potentials in the string theory landscape - IIB/F-theory perspective -
• Holomorphic couplings in non-perturbative string compactifications
• Moduli stabilization in asymptotic flux compactifications
• A local Wheeler-DeWitt measure for the string landscape
• Estimating Calabi-Yau hypersurface and triangulation counts with equation learners
• The dark universe after reheating in string inflation
• Classical transitions with the topological number changing in the early Universe
• Accessibility measure for eternal inflation: dynamical criticality and higgs metastability
• The self-organized critical multiverse
• Search optimization, funnel topography, and dynamical criticality on the string landscape
• Computational complexity of the landscape. II: Cosmological considerations
• Machine learning in the string landscape
• Artificial neural network in cosmic landscape
• Data science applications to string theory

This page was built for publication: Computational complexity of the landscape. I.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q877685)