Polynomial-Time Homology for Simplicial Eilenberg-MacLane Spaces

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Polynomial-Time Homology for Simplicial Eilenberg-MacLane Spaces

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

Polynomial-Time Homology for Simplicial Eilenberg-MacLane Spaces

Popis výsledku anglicky

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

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2013

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Foundations of Computational Mathematics

ISSN

1615-3375

e-ISSN

—

Svazek periodika

13

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

29

Strana od-do

935-963

Kód UT WoS článku

000326735300004

EID výsledku v databázi Scopus

—