Complexity in rational homotopy
type: Item
instance of: scholarly article
title: Complexity in rational homotopy
zbMATH Open document ID: 0933.55014
DOI: 10.1016/S0040-9383(98)00059-7
author: Luis Lechuga
author: Aniceto Murillo
published in: Topology
publication date: 2000-04-04T00:00:00Z
review text: Rational homotopy theory replaces spaces by their minimal models and gives therefore a procedure to compute quite easily the rational homotopy invariants of the spaces. However, this is not so easy because the complexity of the problems grows in general exponentially. In [Ann. Math., II. Ser. 122, 87-112 (1985; Zbl 0584.13012)] \textit{D. J. Anick} has already shown that some problems are NP-hard. In this paper the authors show that in the class of 1-connected spaces \(S\) for which \(\Pi_*(S)\otimes \mathbb{Q}\) is finite-dimensional, determining whether \(H^*(S,\mathbb{Q})\) is finite-dimensional, is an NP-hard problem. They also show that the computation of the category of Betti numbers of formal spaces are NP-hard problems. To prove these theorems they establish a new link between homotopy and graph theory. For any \(k\geq 2\) and any finite graph \(G\) they build a space whose rational cohomology is finite-dimensional if and only if \(G\) is \(k\)-colorable.
Mathematics Subject Classification ID: 55P62
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1356311
zbMATH Keywords: rational homotopy theory
zbMATH Keywords: graph theory
reviewed by: Yves Félix
MaRDI profile type: Publication
full work available at URL: s0040-9383(98)00059-7
OpenAlex ID: W2101202120
Recommended article: Q3805463
Recommended article: Complexification and homotopy
Recommended article: Rational homotopy type and computability
Recommended article: Q4505020
Recommended article: Rational homotopy and intersection-formality of complex algebraic varieties
Recommended article: Homology versus homotopy in rational fibrations
Recommended article: Rational obstruction theory and rational homotopy sets
Recommended article: Rational homotopy theory for non-simply connected spaces
Recommended article: Q4607960
Recommended article: Q4896553
description: scientific article; zbMATH DE number 1356311