Extendability of continuous maps is undecidable

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 A\subseteq X, and a (c...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2013-02
Main Authors: Cadek, Martin, Krcal, Marek, Matousek, Jiri, Vokrinek, Lukas, Wagner, Uli
Format: Article
Language:English
Subjects:
Algorithms
Complexity
Computation
Polynomials
Topology
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 A\subseteq X, and a (continuous) map f:A->Y, decide whether f can be extended to a continuous map \bar{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
ISSN:2331-8422