  For several computational problems in homotopy theory, we obtain algorithms
with running time polynomial in the input size. In particular, for every fixed
k>1, there is a polynomial-time algorithm that, for a 1-connected topological
space X given as a finite simplicial complex, or more generally, as a
simplicial set with polynomial-time homology, computes the k-th homotopy group
\pi_k(X), as well as the first k stages of a Postnikov system of X. Combined
with results of an earlier paper, this yields a polynomial-time computation of
[X,Y], i.e., all homotopy classes of continuous mappings X -> Y, under the
assumption that Y is (k-1)-connected and dim X < 2k-1. We also obtain a
polynomial-time solution of the extension problem, where the input consists of
finite simplicial complexes X,Y, where Y is (k-1)-connected and dim X < 2k,
plus a subspace A\subseteq X and a (simplicial) map f:A -> Y, and the question
is the extendability of f to all of X.
  The algorithms are based on the notion of a simplicial set with
polynomial-time homology, which is an enhancement of the notion of a simplicial
set with effective homology developed earlier by Sergeraert and his co-workers.
Our polynomial-time algorithms are obtained by showing that simplicial sets
with polynomial-time homology are closed under various operations, most
notably, Cartesian products, twisted Cartesian products, and classifying space.
One of the key components is also polynomial-time homology for the
Eilenberg--MacLane space K(Z,1), provided in another recent paper by Krcal,
Matousek, and Sergeraert.
