The computation of the Betti numbers of an elliptic space is an NP-hard problem

DOI10.1016/S0166-8641(02)00340-1zbMath1023.55004OpenAlexW2145185058MaRDI QIDQ1398203

Antonio Garvín, Luis Lechuga

Publication date: 29 July 2003

Published in: Topology and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-8641(02)00340-1

zbMATH Keywords

complexityNP-hard problemrational homotopy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Rational homotopy theory (55P62) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Homology and cohomology theories in algebraic topology (55N99)

Related Items (2)

Non-formal homogeneous spaces ⋮ Computational Complexity of Topological Invariants

Cites Work

• Finite computability of Postnikov complexes
• Diophantine equations, Hilbert series, and undecidable spaces
• Complexity in rational homotopy
• Unnamed Item
• Unnamed Item

This page was built for publication: The computation of the Betti numbers of an elliptic space is an NP-hard problem