Extending Continuous Maps: Polynomiality and Undecibility

Warning

This publication doesn't include Institute of Computer Science. It includes Faculty of Science. Official publication website can be found on muni.cz.

Authors	ČADEK Martin KRČÁL Marek MATOUŠEK Jiří VOKŘÍNEK Lukáš WAGNER Uli
Year of publication	2013
Type	Article in Proceedings
Conference	Proceedings of the 45th annual ACM symposium on Symposium on theory of computing
MU Faculty or unit	Faculty of Science
Citation
web	http://dl.acm.org/citation.cfm?doid=2488608.2488683
Doi	https://doi.org/10.1145/2488608.2488683
Field	General mathematics
Keywords	homotopy classes of maps; Postnikov system; algorithm;polynomiality;undecibility
Description	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.
Related projects:	Ústav Eduarda Čecha pro algebru, geometrii a matematickou fyziku