Computational complexity of topological invariants

We answer the following question posed by Lechuga: Given a simply-connected space $X$ with both $H_*(X,\qq)$ and $π_*(X)\otimes \qq$ being finite-dimensional, what is the computational complexity of an algorithm computing the cup-length and the rational Lusternik--Schnirelmann category of $X$? Basically, by a reduction from the decision problem whether a given graph is $k$-colourable (for $k\geq 3$) we show that (even stricter versions of the) problems above are $\mathbf{NP}$-hard.

No reviews yet.

No comments yet.