Extending continuous maps, polynomiality and undecidability

DOI10.1145/2488608.2488683MaRDI QIDQ5495830zbMATH OpenOpenAlexFDO

Authors Martin Čadek, Marek Krčál, Lukáš Vokřínek, Jiří Matoušek, Uli Wagner

Publication date 7 August 2014

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.2370

zbMATH Keywords

algebraic topologyextendabilityhomotopy groupshomotopy theory

Mathematics Subject Classification ID

Homotopy groups (55Q99) Simplicial sets and complexes in algebraic topology (55U10) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Abstract: We consider two basic problems of algebraic topology, the extension problem and the computation of higher homotopy groups, from the point of view of computability and computational complexity. The extension problem is the following: Given topological spaces X and Y, a subspace Asubseteq X, and a (continuous) map f:A->Y, decide whether f can be extended to a continuous map �ar{f}:X->Y. All spaces are given as finite simplicial complexes and the map f is simplicial. Recent positive algorithmic results, proved in a series of companion papers, show that for (k-1)-connected Y, k>=2, the extension problem is algorithmically solvable if the dimension of X is at most 2k-1, and even in polynomial time when k is fixed. Here we show that the condition dim X<=2k-1 cannot be relaxed: for dim X=2k, the extension problem with (k-1)-connected Y becomes undecidable. Moreover, either the target space Y or the pair (X,A) can be fixed in such a way that the problem remains undecidable. Our second result, a strengthening of a result of Anick, says that the computation of pi_k(Y) of a 1-connected simplicial complex Y is #P-hard when k is considered as a part of the input.

Recommendations

• Extendability of continuous maps is undecidable
• Computing all maps into a sphere
• Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension
• Decidability of the extension problem for maps into odd-dimensional spheres
• Algorithmic solvability of the lifting-extension problem

Cited in

(13)

• Reachability problems in nondeterministic polynomial maps on the integers
• Computing simplicial representatives of homotopy group elements
• Algorithmic solvability of the lifting-extension problem
• Extendability of continuous maps is undecidable
• Extendability of simplicial maps is undecidable
• Computing all maps into a sphere
• scientific article; zbMATH DE number 3915627 (Why is no real title available?)
• Sparse Kneser graphs are Hamiltonian
• Decidability of the extension problem for maps into odd-dimensional spheres
• Computational complexity of topological invariants
• Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension
• Computing all maps into a sphere
• Rational homotopy type and computability

This page was built for publication: Extending continuous maps, polynomiality and undecidability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495830)