Computational Complexity of Topological Invariants
Manuel Amann · Proceedings of the Edinburgh Mathematical Society · 2014
Abstract We answer the following question posed by Lechuga: given a simply connected spaceXwith bothH*(X; ℚ) and π*(X) ⊗ ℚ being finite dimensional, what is the computational complexity of an algorithm computing the cup length and the rational Lusternik—Schnirelmann category ofX? Basically, by a reduction from the decision problem of whether a given graph isk-colourable fork≥ 3, we show that even stricter versions of the problems above are NP-hard.