Computational complexity of topological invariants

Details Computational complexity of topological invariants Computational complexity of topological invariants

2011-12-05

arxiv.org/abs/1112.0812v1

Mathematics

Algebraic Topology

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Computational complexity of topological invariants does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computational complexity of topological invariants, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computational complexity of topological invariants will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-393270