Extendability of Continuous Maps Is Undecidable

Kód výsledku v IS VaVaI

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

Nalezeny alternativní kódy

RIV/00216224:14310/14:00073472

Výsledek na webu

<a href="http://dx.doi.org/10.1007/s00454-013-9551-8" target="_blank" >http://dx.doi.org/10.1007/s00454-013-9551-8</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00454-013-9551-8" target="_blank" >10.1007/s00454-013-9551-8</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Extendability of Continuous Maps Is Undecidable

Popis výsledku v původním jazyce

We consider two basic problems of algebraic topology: the extension problem and the computation of higher homotopy groups, from the point of view of computability and computational complexity. The extension problem is the following: Given topological spaces X and Y, a subspace AaS dagger X, and a (continuous) map f:A -> Y, decide whether f can be extended to a continuous map . All spaces are given as finite simplicial complexes, and the map f is simplicial. Recent positive algorithmic results, proved ina series of companion papers, show that for (k-1)-connected Y, ka parts per thousand yen2, the extension problem is algorithmically solvable if the dimension of X is at most 2k-1, and even in polynomial time when k is fixed. Here we show that the condition cannot be relaxed: for , the extension problem with (k-1)-connected Y becomes undecidable. Moreover, either the target space Y or the pair (X,A) can be fixed in such a way that the problem remains undecidable. Our second result, a str

Název v anglickém jazyce

Extendability of Continuous Maps Is Undecidable

Popis výsledku anglicky

We consider two basic problems of algebraic topology: the extension problem and the computation of higher homotopy groups, from the point of view of computability and computational complexity. The extension problem is the following: Given topological spaces X and Y, a subspace AaS dagger X, and a (continuous) map f:A -> Y, decide whether f can be extended to a continuous map . All spaces are given as finite simplicial complexes, and the map f is simplicial. Recent positive algorithmic results, proved ina series of companion papers, show that for (k-1)-connected Y, ka parts per thousand yen2, the extension problem is algorithmically solvable if the dimension of X is at most 2k-1, and even in polynomial time when k is fixed. Here we show that the condition cannot be relaxed: for , the extension problem with (k-1)-connected Y becomes undecidable. Moreover, either the target space Y or the pair (X,A) can be fixed in such a way that the problem remains undecidable. Our second result, a str

Druh

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

CEP obor

BD - Teorie informace

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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

Discrete and Computational Geometry

ISSN

0179-5376

e-ISSN

—

Svazek periodika

51

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

43

Strana od-do

24-66

Kód UT WoS článku

000329619100002

EID výsledku v databázi Scopus

—