Abstract
We consider several basic problems of algebraic topology, with connections to combinatorial and geometric questions, from the point of view of computational complexity. The extension problem asks, given topological spaces X,Y, a subspace A SUBSET OF OR EQUAL TO X, and a (continuous) map f:A -> Y, whether f can be extended to a map X -> Y.
For computational purposes, we assume that X and Y are represented as finite simplicial complexes, A is a subcomplex of X, and f is given as a simplicial map. In this generality the problem is undecidable, as follows from Novikov's result from the 1950s on uncomputability of the fundamental group π1(Y).
We thus study the problem under the assumption that, for some k GREATER-THAN OR EQUAL TO 2, Y is (k-1)-connected; informally, this means that Y has "no holes up to dimension k-1" i.e., the first k-1 homotopy groups of Y vanish (a basic example of such a Y is the sphere Sk). We prove that, on the one hand, this problem is still undecidable for dim X=2k.
On the other hand, for every fixed k GREATER-THAN OR EQUAL TO 2, we obtain an algorithm that solves the extension problem in polynomial time assuming Y (k-1)-connected and dim X LESS-THAN OR EQUAL TO 2k-1$. For dim X LESS-THAN OR EQUAL TO 2k-2, the algorithm also provides a classification of all extensions up to homotopy (continuous deformation).
This relies on results of our SODA 2012 paper, and the main new ingredient is a machinery of objects with polynomial-time homology, which is a polynomial-time analog of objects with effective homology developed earlier by Sergeraert et al. We also consider the computation of the higher homotopy groups πk(Y)$, k GREATER-THAN OR EQUAL TO 2, for a 1-connected Y.
Their computability was established by Brown in 1957; we show that πk(Y) can be computed in polynomial time for every fixed k GREATER-THAN OR EQUAL TO 2.