  We answer the following question posed by Lechuga: Given a simply-connected
space $X$ with both $H_*(X,\qq)$ and $\pi_*(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.
