Extending Continuous Maps: Polynomiality and Undecibility

Investor logo

Warning

This publication doesn't include Faculty of Medicine. 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 http://dx.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:

You are running an old browser version. We recommend updating your browser to its latest version.

More info