Complexity in rational homotopy (Q1806114)

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.