Polynomial-Time Homology for Simplicial Eilenberg-MacLane Spaces
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F13%3A10159291" target="_blank" >RIV/00216208:11320/13:10159291 - isvavai.cz</a>
Result on the web
<a href="http://link.springer.com/article/10.1007%2Fs10208-013-9159-7" target="_blank" >http://link.springer.com/article/10.1007%2Fs10208-013-9159-7</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s10208-013-9159-7" target="_blank" >10.1007/s10208-013-9159-7</a>
Alternative languages
Result language
angličtina
Original language name
Polynomial-Time Homology for Simplicial Eilenberg-MacLane Spaces
Original language description
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: weshow that the Eilenberg-MacLane space , 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 . The construction is purely combinatorial and it can be understood as a certain procedure for reducing finite sequences of integers, wi
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Foundations of Computational Mathematics
ISSN
1615-3375
e-ISSN
—
Volume of the periodical
13
Issue of the periodical within the volume
6
Country of publishing house
US - UNITED STATES
Number of pages
29
Pages from-to
935-963
UT code for WoS article
000326735300004
EID of the result in the Scopus database
—