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.

Basic information

Original name

Extending Continuous Maps: Polynomiality and Undecibility

Name in Czech

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

Authors

ČADEK, Martin (203 Czech Republic, guarantor, belonging to the institution), Marek KRČÁL (203 Czech Republic), Jiří MATOUŠEK (203 Czech Republic), Lukáš VOKŘÍNEK (203 Czech Republic, belonging to the institution) and Uli WAGNER (756 Switzerland)

Edition

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

Publisher

Association for Computing Machinery

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10101 Pure mathematics

Country of publisher

United States of America

Confidentiality degree

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

Publication form

printed version "print"

References:

URL

RIV identification code

RIV/00216224:14310/13:00066242

Organization unit

Faculty of Science

ISBN

978-1-4503-2029-0

DOI

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

Keywords in English

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

Abstract

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.

In Czech

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

Links

GBP201/12/G028, research and development project

Name: Ústav Eduarda Čecha pro algebru, geometrii a matematickou fyziku

Investor: Czech Science Foundation

Citovat

ČADEK, Martin, Marek KRČÁL, Jiří MATOUŠEK, Lukáš VOKŘÍNEK and 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, p. 595-604. ISBN 978-1-4503-2029-0. Available from: 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 and 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, p.~595-604. ISBN~978-1-4503-2029-0. Available from: https://dx.doi.org/10.1145/2488608.2488683.

Detailed Information on Publication Record