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