Computational Complexity of Vacua and Near-Vacua in Field and String Theory

Abstract

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 $\ne$ 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.

arXiv comment9 pages. PRD Version

References in corpus (39)

• de Sitter Vacua in String Theory
• Supergravity description of field theories on curved manifolds and a no go theorem
• Systematics of Moduli Stabilisation in Calabi-Yau Flux Compactifications
• Distributions of flux vacua
• Counting Flux Vacua
• The Number of Eigenvalues of a Tensor
• On the de Sitter swampland criterion
• Probabilities in the inflationary multiverse
• De Sitter vs Quintessence in String Theory
• The dS swampland conjecture and the Higgs potential
• Computational complexity of the landscape I
• Explicit de Sitter Flux Vacua for Global String Models with Chiral Matter
• F-Theory Compactifications with Multiple U(1)-Factors: Constructing Elliptic Fibrations with Rational Sections
• Complexity of random smooth functions on the high-dimensional sphere
• NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems
• Machine Learning in the String Landscape
• Machine Learning of Calabi-Yau Volumes
• Cohomology of Line Bundles: A Computational Algorithm
• The Wasteland of Random Supergravities
• Global F-theory Models: Instantons and Gauge Dynamics
• Evolving neural networks with genetic algorithms to study the String Landscape
• Heterotic MSSM on a Resolved Orbifold
• On Algorithmic Universality in F-theory Compactifications
• Machine Learning Line Bundle Cohomologies of Hypersurfaces in Toric Varieties
• Terminal Singularities, Milnor Numbers, and Matter in F-theory
• The de Sitter swampland conjecture and supersymmetric AdS vacua
• de Sitter extrema and the swampland
• Quantum Corrections and the de Sitter Swampland Conjecture
• Scanning the skeleton of the 4D F-theory landscape
• The F-theory geometry with most flux vacua
• A New Method for Finding Vacua in String Phenomenology
• Vacuum Selection from Cosmology on Networks of String Geometries
• Three Looks at Instantons in F-theory -- New Insights from Anomaly Inflow, String Junctions and Heterotic Duality
• Computational complexity of the landscape II - Cosmological considerations
• On the computation of non-perturbative effective potentials in the string theory landscape -- IIB/F-theory perspective
• Fast optimization algorithms and the cosmological constant
• A perfect match of MSSM-like orbifold and resolution models via anomalies
• The Toric SO(10) F-Theory Landscape
• The Multivariate Resultant is NP-hard in any Characteristic

Cited by in corpus (27)

• Small Cosmological Constants in String Theory
• Branes with Brains: Exploring String Vacua with Deep Reinforcement Learning
• On String Theory Expectations for Photon Couplings to Axion-Like Particles
• Searching the Landscape of Flux Vacua with Genetic Algorithms
• Moduli Stabilization in Asymptotic Flux Compactifications
• Getting CICY High
• The Calabi-Yau Landscape: from Geometry, to Physics, to Machine-Learning
• Distinguishing Elliptic Fibrations with AI
• Machine learning for complete intersection Calabi-Yau manifolds: a methodological study
• Estimating Calabi-Yau Hypersurface and Triangulation Counts with Equation Learners
• The Self-Organized Critical Multiverse
• Search Optimization, Funnel Topography, and Dynamical Criticality on the String Landscape
• Accessibility Measure for Eternal Inflation: Dynamical Criticality and Higgs Metastability
• Revealing systematics in phenomenologically viable flux vacua with reinforcement learning
• Deep multi-task mining Calabi-Yau four-folds
• Inflation, Swampland, and Landscape
• Early-Time Measure in Eternal Inflation
• Kahler Moduli Stabilization and the Propagation of Decidability
• Ising Machines for Diophantine Problems in Physics
• On the Search for Low $W_0$
• Constraints on Standard Model Constructions in F-theory
• Deep learning complete intersection Calabi-Yau manifolds
• A Cosmological Constant That is Too Small
• ALP Anarchy
• Faking Gauge Coupling Unification in String Theory
• Joint Statistics of Cosmological Constant and SUSY Breaking in Flux Vacua with Nilpotent Goldstino
• Probing the Structure of String Theory Vacua with Genetic Algorithms and Reinforcement Learning