Computing All Maps into a Sphere

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F14%3A10286490" target="_blank" >RIV/00216208:11320/14:10286490 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216224:14310/14:00075900

Výsledek na webu

<a href="http://dx.doi.org/10.1145/2597629" target="_blank" >http://dx.doi.org/10.1145/2597629</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/2597629" target="_blank" >10.1145/2597629</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Computing All Maps into a Sphere

Popis výsledku v původním jazyce

Given topological spaces X, Y, a fundamental problem of algebraic topology is understanding the structure of all continuous maps X -> Y. We consider a computational version, where X, Y are given as finite simplicial complexes, and the goal is to compute[X, Y], that is, all homotopy classes of such maps. We solve this problem in the stable range, where for some d > 1, we have dim X < 2d - 1 and Y is (d - 1)-connected; in particular, Y can bathed-dimensional sphere S-d. The algorithm combines classical tools and ideas from homotopy theory (obstruction theory, Postnikov systems, and simplicial sets) with algorithmic tools froth effective algebraic topology (locally effective simplicial sets and objects with effective homology). In contrast, [X, Y] is known to be uncomputable for general X, Y, since for X = S-1 it includes a well known undecidable problem: testing triviality of the fundamental group of Y. In follow-up papers, the algorithm is shown to run in polynomial time for d fixed, a

Název v anglickém jazyce

Computing All Maps into a Sphere

Popis výsledku anglicky

Given topological spaces X, Y, a fundamental problem of algebraic topology is understanding the structure of all continuous maps X -> Y. We consider a computational version, where X, Y are given as finite simplicial complexes, and the goal is to compute[X, Y], that is, all homotopy classes of such maps. We solve this problem in the stable range, where for some d > 1, we have dim X < 2d - 1 and Y is (d - 1)-connected; in particular, Y can bathed-dimensional sphere S-d. The algorithm combines classical tools and ideas from homotopy theory (obstruction theory, Postnikov systems, and simplicial sets) with algorithmic tools froth effective algebraic topology (locally effective simplicial sets and objects with effective homology). In contrast, [X, Y] is known to be uncomputable for general X, Y, since for X = S-1 it includes a well known undecidable problem: testing triviality of the fundamental group of Y. In follow-up papers, the algorithm is shown to run in polynomial time for d fixed, a

Druh

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

CEP obor

BD - Teorie informace

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2014

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

Journal of the ACM

ISSN

0004-5411

e-ISSN

—

Svazek periodika

61

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

46

Strana od-do

1-46

Kód UT WoS článku

000337201400003

EID výsledku v databázi Scopus

—