Computing Homotopy Classes for Diagrams

We present an algorithm that, given finite diagrams of simplicial sets X, A, Y, i.e., functors [Formula: see text] , such that (X, A) is a cellular pair, [Formula: see text] , [Formula: see text] , computes the set [Formula: see text] of homotopy classes of maps of diagrams [Formula: see text] extending a given [Formula: see text] . For fixed [Formula: see text] , the running time of the algorithm is polynomial. When the stability condition is dropped, the problem is known to be undecidable. Using Elmendorf’s theorem, we deduce an algorithm that, given finite simplicial sets X, A, Y with an action of a finite group G, computes the set [Formula: see text] of homotopy classes of equivariant maps [Formula: see text] extending a given equivariant map [Formula: see text] under the stability assumption [Formula: see text] and [Formula: see text] , for all subgroups [Formula: see text] . Again, for fixed [Formula: see text] , the algorithm runs in polynomial time. We further apply our results to Tverberg-type problem in computational topology: Given a k-dimensional simplicial complex K, is there a map [Formula: see text] without r-tuple intersection points? In the metastable range of dimensions, [Formula: see text] , the problem is shown algorithmically decidable in polynomial time when k, d, and r are fixed.