Computational complexity of the landscape I

Frederik Denef (KU Leuven); IHES); Michael R. Douglas (Rutgers

RECORD

Computational complexity of the landscape I

Frederik Denef (KU Leuven), Michael R. Douglas (Rutgers, IHES)

High Energy Physics - Theory · Submitted 7 Feb 2006

abstract compiled · 2026-09-23 · no language-model review

The authors' main claim 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.

how it is stated · asserted 0.99 read the record →

Comment (0) Read on arXiv ↗

Cite ▾

arXiv IDhep-th/0602072 (version 2)

Pith IDNZDFL3MX, Pith's permanent record of this paper and its review

CitationFrederik Denef (KU Leuven), IHES), Michael R. Douglas (Rutgers. "Computational complexity of the landscape I." arXiv:hep-th/0602072 (2006). https://pith.science/paper/NZDFL3MX

Claim paper

The compiled record

The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Open the compiled record

Compiled by classifier-1.13-20260917 via OpenRouter, question bank abstract-p1-20260923, 2026-09-23: 1 request, 3,603 input tokens, $0.0002 reported.

What the abstract itself states, as probabilities: claims first 0.05 · states limitation 0.70 · human participants 0.01 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.22 · compares with prior results 0.08 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v2. Results and the main claim are underlined; show every role.

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.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	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.	contribution 0.59	0.93	0.92	asserted 0.99
s1	In particular, we prove that in the Bousso-Polchinski model, the problem is NP complete.	result 0.98	0.94	0.25	asserted 1.00
s2	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.	interpretation 1.00	0.21	0.10	speculative 0.57
s3	In a companion paper, we apply this point of view to the question of how early cosmology might select a vacuum.	future work 0.98	0.42	0.02	asserted 0.87

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v2

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

The paper

Original 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.

Human review

How Pith checks papers → · Full audit of this paper →

References

Forward citations

Cited by 25 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Flux Vacua, Asymptotic Periods, and Relatively Anosov Representations
hep-th 2026-10 conditional novelty 8.0 of 10

A topological index computed from boundary data guarantees the existence of flux vacua in the interior of moduli space for one-modulus Calabi-Yau fourfolds.
Quantum Computation vs. Firewalls
hep-th 2013-01 conditional novelty 8.0 of 10

Decoding the Hawking radiation needed to test the AMPS firewall argument requires a quantum computation exponential in the black hole entropy, which exceeds the lifetime of Schwarzschild, charged, and boxed black hole...
Higgs Bundles and UV Completion in F-Theory
hep-th 2009-04 accept novelty 8.0 of 10

Local F-theory GUT models are equivalent to spectral covers, which forbids three-generation SU(5) models at generic moduli but permits explicit three-generation constructions on the Noether-Lefschetz locus.
The QCD Axion and Moduli Stabilisation
hep-th 2006-02 conditional novelty 7.0 of 10

A clean supergravity no-go theorem forbids supersymmetric moduli stabilization with a flat QCD axion, and a large-volume construction gives f_a approximately the geometric mean of the Planck and SUSY-breaking scales.
A Cosmological Constant That is Too Small
hep-th 2021-07 conditional novelty 6.0 of 10

A type IIB flux compactification on an orientifold of a Calabi-Yau threefold yields a supersymmetric AdS4 vacuum with vacuum energy about 10^-144 Planck units and Kaluza-Klein radius about 10^4 Planck lengths.

Show 20 more citing papers

Branes with Brains: Exploring String Vacua with Deep Reinforcement Learning
hep-th 2019-03 conditional novelty 6.0 of 10

An asynchronous advantage actor-critic learns to solve the tadpole, K-theory and supersymmetry Diophantine conditions of type IIA intersecting-brane compactifications, outperforming random search by factors of 20 to 200.
Higher Spin de Sitter Hilbert Space
hep-th 2017-11 conditional novelty 6.0 of 10

A 2N-field Gaussian boundary model is proposed as the exact Hilbert space of minimal higher spin de Sitter gravity, reproducing the earlier Sp(N) proposal at large N and yielding closed-form late-time correlators.
Machine Learning in the String Landscape
hep-th 2017-07 conditional novelty 6.0 of 10

A logistic regression trained on random F-theory geometries generated a conjecture about when an E6 gauge group appears, which the authors then proved and confirmed against independent random samples.
On Algorithmic Universality in F-theory Compactifications
hep-th 2017-06 conditional novelty 6.0 of 10

A tree-blowup construction algorithm generates roughly 10^755 F-theory geometries in which non-Higgsable seven-branes and gauge rank above 160 occur with probability near one.
Tuning and Backreaction in F-term Axion Monodromy Inflation
hep-th 2014-11 conditional novelty 6.0 of 10

A no-go theorem rules out weakly coupled type IIB orientifold realisations of F-term axion monodromy inflation, while Calabi-Yau fourfolds evade it and appear to leave a workable flux landscape.
Inflating in a Better Racetrack
hep-th 2006-03 conditional novelty 6.0 of 10

An explicit type IIB compactification with two Kahler moduli can support racetrack inflation driven by a linear combination of axions, matching the COBE spectrum with n_s approximately 0.95.
Probabilities in the landscape: The decay of nearly flat space
hep-th 2006-03 conditional novelty 6.0 of 10

The decay rate of a false vacuum varies continuously as the false vacuum energy approaches zero from above, so low-energy de Sitter vacua are not anomalously stable compared to the Minkowski vacua they become when the...
Proton Decay, Yukawa Couplings and Underlying Gauge Symmetry in String Theory
hep-th 2006-02 conditional novelty 6.0 of 10

Under the assumptions that all quark and lepton Yukawa couplings come from the super Yang-Mills interactions of an underlying symmetry G and that matter and Higgs fields have different origins in the coset G/SU(5), th...
Tameness and Complexity in Quantum Field Theory and Gravity
hep-th 2026-09 conditional novelty 5.0 of 10

Physical functions and effective quantum gravity theories are tame (definable in o-minimal structures) with finite complexity measurable via sharp o-minimality.
The Computational Complexity of the Weak Gravity Conjecture
hep-th 2025-05 conditional novelty 4.0 of 10

Checking the Convex Hull Weak Gravity Conjecture by explicitly constructing the charge-to-mass convex hull has worst-case runtime exponential in the number of U(1) gauge fields, but the paper also claims a polynomial ...
Searching the Landscape of Flux Vacua with Genetic Algorithms
hep-th 2019-07 conditional novelty 4.0 of 10

Genetic algorithms efficiently locate type IIB flux vacua with target string coupling, superpotential, and mass scales, outperforming random-walk search on two toy models.
What to do with a Ricci-flat Calabi--Yau metric?
hep-th 2026-05 unverdicted novelty 3.0 of 10

Numerical Ricci-flat Calabi–Yau metrics turn string compactifications from topological existence statements into computable geometries, unlocking normalized couplings, spectra, and metric-level tests of mirror symmetry.
Flux Compactification
hep-th 2006-10 accept novelty 3.0 of 10

Fluxes through the compact extra dimensions can stabilize all of string theory's moduli and break supersymmetry, yielding a vast landscape of vacua whose statistics may explain the small cosmological constant.
Understanding the landscape
hep-th 2006-02 unverdicted novelty 3.0 of 10

A position paper arguing that the string theory landscape of vacuum states is more like chemistry than mathematics and proposing tools to study it.
Moduli Stabilization in String Theory
hep-th 2023-10 accept novelty 2.0 of 10

This is a review of moduli stabilization in string compactifications, organizing the KKLT and Large Volume Scenario constructions, their extensions to other string theories, and their cosmological and particle-physics...
The Calabi-Yau Landscape: from Geometry, to Physics, to Machine-Learning
hep-th 2018-12 conditional novelty 2.0 of 10

The draft is a pedagogical survey connecting Calabi-Yau geometry, string-theory model building, computational algebraic geometry, and machine-learning applications, with code examples and dataset pointers for beginners.
Les Houches Lectures on Constructing String Vacua
hep-th 2008-03 unverdicted novelty 2.0 of 10

The paper is a pedagogical review of how F-theory and type IIB flux compactifications are used to construct string vacua with stabilized moduli.
Physics of String Flux Compactifications
hep-th 2007-01 accept novelty 2.0 of 10

Fluxes stabilize string moduli and generate an astronomically large discretuum of vacua whose statistical distribution makes the observed cosmological constant generic and turns the supersymmetry breaking scale into a...
The Cosmological Constant and the String Landscape
hep-th 2006-03 accept novelty 2.0 of 10

This paper argues that the cosmological constant is environmental and selected anthropically within the string landscape, a position that remains influential but unproven.
Inflation and String Theory
hep-th 2014-04 accept novelty 1.0 of 10

A survey arguing that inflation is ultraviolet-sensitive and therefore requires a quantum gravity completion, then cataloguing the string theory constructions that attempt to provide one.

How the literature uses it

43 arXiv papers cite this in 57 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 45 sentences without a confident label

Compares with it 1 paper

This can be compared with the problem of [ref] , which was to identify the fluxes and other compactification parameters of a vacuum with $|Λ|≤Λ_max$ in the BP model and other toy landscape models through pure computation (not simulation).

Computational complexity of the landscape II - Cosmological considerations · Complexity class of a cosmology · 0.98

Cites it as support 2 papers

Moreover, for deterministic algorithms, difficulties due to the large size of the landscape are exacerbated by computational complexity, as can be seen in several toy models [ref] .

Searching the Landscape of Flux Vacua with Genetic Algorithms · Introduction · 0.96
For instance, the search for small cosmological constants in simplified idealized models is already NP-hard [ref] , although the success in finding explicit solutions with small cosmological constant in F-theory [ref] suggests that the structure of the landscape may enable efficient solutions to this problem.

Snowmass White Paper: String Theory and Particle Physics · Machine Learning and Computational Complexity · 0.96

Cites it as background 8 papers

In 2007, Denef and Douglas brought a complexity theoretic perspective to the cosmological constant problem [ref] .

Fast optimization algorithms and the cosmological constant · Computational Complexity · 0.89
In string phenomenology context, computability theory has helped to assess whether the problem of finding vacua is feasible by a Turing machine [ref] .

The Computational Complexity of the Weak Gravity Conjecture · Introduction · 0.81
See [ref] and [ref] for an exposition of some of the problems involved.

Life at the Interface of Particle Physics and String Theory · Predictive Landscapes · 0.81

Discussion

Know something about this paper? Leave a comment, or highlight any passage above to comment on it.