Computer Science – Computational Geometry
Scientific paper
2012-01-30
Computer Science
Computational Geometry
30 pages
Scientific paper
In an earlier paper of Cadek, Vokrinek, Wagner, and the present authors, we investigated an algorithmic problem in computational algebraic topology, namely, the computation of all possible homotopy classes of maps between two topological spaces, under suitable restriction on the spaces. We aim at showing that, if the dimensions of the considered spaces are bounded by a constant, then the computations can be done in polynomial time. In this paper we make a significant technical step towards this goal: we show that the Eilenberg-MacLane space K(Z,1), represented as a simplicial group, can be equipped with polynomial-time homology (this is a polynomial-time version of effective homology considered in previous works of the third author and co-workers). To this end, we construct a suitable discrete vector field, in the sense of Forman's discrete Morse theory, on K(Z,1). The construction is purely combinatorial and it can be understood as a certain procedure for reducing finite sequences of integers, without any reference to topologyThe Eilenberg--MacLane spaces are the basic building blocks in a Postnikov system, which is a "layered" representation of a topological space suitable for homotopy-theoretic computations. Employing the result of this paper together with some other results on polynomial-time homology, which we intend to present in another paper, we hope to obtain, for every fixed k, a polynomial-time algorithm for computing the k-th homotopy group \pi_k(X) of a given simply connected space X, as well as the first k stages of a Postnikov system for X, and also a polynomial-time version of the algorithm of Cadek et al. mentioned above.
Krcal Marek
Matoušek Jiří
Sergeraert Francis
No associations
LandOfFree
Polynomial-time homology for simplicial Eilenberg-MacLane spaces 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 Polynomial-time homology for simplicial Eilenberg-MacLane spaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial-time homology for simplicial Eilenberg-MacLane spaces will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-359619