Extending Continuous Maps: Polynomiality and Undecibility

D 2013

Extending Continuous Maps: Polynomiality and Undecibility

ČADEK, Martin, Marek KRČÁL, Jiří MATOUŠEK, Lukáš VOKŘÍNEK, Uli WAGNER et. al.

Základní údaje

Originální název

Extending Continuous Maps: Polynomiality and Undecibility

Název česky

Rozšiřování spojitých zobrazení: polynomialita a nerozhodnutelnost

Autoři

ČADEK, Martin (203 Česká republika, garant, domácí), Marek KRČÁL (203 Česká republika), Jiří MATOUŠEK (203 Česká republika), Lukáš VOKŘÍNEK (203 Česká republika, domácí) a Uli WAGNER (756 Švýcarsko)

Vydání

New York, USA, Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, od s. 595-604, 10 s. 2013

Nakladatel

Association for Computing Machinery

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10101 Pure mathematics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Odkazy

URL

Kód RIV

RIV/00216224:14310/13:00066242

Organizační jednotka

Přírodovědecká fakulta

ISBN

978-1-4503-2029-0

DOI

http://dx.doi.org/10.1145/2488608.2488683

Klíčová slova anglicky

homotopy classes of maps; Postnikov system; algorithm;polynomiality;undecibility

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 8. 7. 2013 17:43, doc. RNDr. Martin Čadek, CSc.

Anotace

ORIG CZ

V originále

We show that for fixed k the k-th homotopy group of a finite simply connected simplicial complex is polynomial-time computable. Simultaneously, we prove that the problem of extending a continuous map to simply connected space is undecidable in general.

Česky

Pro pevné k lze provést výpočet k-té homotopické grupy v polynomiálním čase. Z druhé strany, problém zda lze dané zobrazením do jednoduše souvislé simpliciální množiny rozšířit je nerozhodnutelný.

Návaznosti

GBP201/12/G028, projekt VaV

Název: Ústav Eduarda Čecha pro algebru, geometrii a matematickou fyziku

Investor: Grantová agentura ČR, Ústav Eduarda Čecha pro algebru, geometrii a matematickou fyziku

Citovat

ČADEK, Martin, Marek KRČÁL, Jiří MATOUŠEK, Lukáš VOKŘÍNEK a Uli WAGNER. Extending Continuous Maps: Polynomiality and Undecibility. In Joan Feigenbaum. Proceedings of the 45th annual ACM symposium on Symposium on theory of computing. New York, USA: Association for Computing Machinery, 2013, s. 595-604. ISBN 978-1-4503-2029-0. Dostupné z: https://dx.doi.org/10.1145/2488608.2488683.

@inproceedings{1115119,
   author = {Čadek, Martin and Krčál, Marek and Matoušek, Jiří and Vokřínek, Lukáš and Wagner, Uli},
   address = {New York, USA},
   booktitle = {Proceedings of the 45th annual ACM symposium on Symposium on theory of computing},
   doi = {http://dx.doi.org/10.1145/2488608.2488683},
   editor = {Joan Feigenbaum},
   keywords = {homotopy classes of maps; Postnikov system; algorithm;polynomiality;undecibility},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {New York, USA},
   isbn = {978-1-4503-2029-0},
   pages = {595-604},
   publisher = {Association for Computing Machinery},
   title = {Extending Continuous Maps: Polynomiality and Undecibility},
   url = {http://dl.acm.org/citation.cfm?doid=2488608.2488683},
   year = {2013}
}

TY  - JOUR
ID  - 1115119
AU  - Čadek, Martin - Krčál, Marek - Matoušek, Jiří - Vokřínek, Lukáš - Wagner, Uli
PY  - 2013
TI  - Extending Continuous Maps: Polynomiality and Undecibility
PB  - Association for Computing Machinery
CY  - New York, USA
SN  - 9781450320290
KW  - homotopy classes of maps
KW  - Postnikov system
KW  - algorithm;polynomiality;undecibility
UR  - http://dl.acm.org/citation.cfm?doid=2488608.2488683
L2  - http://dl.acm.org/citation.cfm?doid=2488608.2488683
N2  - We show that for fixed k the k-th homotopy group of a finite simply connected simplicial complex is polynomial-time computable. Simultaneously, we prove that the problem of extending a continuous map to simply connected space is undecidable in general.
ER  -

ČADEK, Martin, Marek KRČÁL, Jiří MATOUŠEK, Lukáš VOKŘÍNEK a Uli WAGNER. Extending Continuous Maps: Polynomiality and Undecibility. In Joan Feigenbaum. \textit{Proceedings of the 45th annual ACM symposium on Symposium on theory of computing}. New York, USA: Association for Computing Machinery, 2013, s.~595-604. ISBN~978-1-4503-2029-0. Dostupné z: https://dx.doi.org/10.1145/2488608.2488683.

Podrobný výpis o publikaci