No CrossRef data available.
Article contents
Computational Complexity of Topological Invariants
Published online by Cambridge University Press: 11 December 2014
Abstract
We answer the following question posed by Lechuga: given a simply connected space X with both H* (X; ℚ) and π*(X) ⊗ ℚ 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 of whether a given graph is k-colourable for k ≥ 3, we show that even stricter versions of the problems above are NP-hard.
MSC classification
- Type
- Research Article
- Information
- Proceedings of the Edinburgh Mathematical Society , Volume 58 , Issue 1 , February 2015 , pp. 27 - 32
- Copyright
- Copyright © Edinburgh Mathematical Society 2015