A central problem of algebraic topology is to understand the homotopy groups πd(X) of a topological space X. For the computational version of the problem, it is well known that there is no algorithm to decide whether the fundamental group π1(Χ) of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with π1(Χ) trivial), compute the higher homotopy group πd(X) for any given d ≥ 2. However, these algorithms come with a caveat: They compute the isomorphism type of πd(Χ), d ≥ 2 as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of πd(Χ). Converting elements of this abstract group into explicit geometric maps from the d-dimensional sphere Sd to Χ has been an important open question in the emerging field of computational homotopy theory. Here we present an algorithm that, given a simply connected simplicial complex Χ, computes πd(Χ) and represents its elements as simplicial maps from a suitable triangulation of the d-sphere Sd to Χ. For fixed d, the algorithm runs in time exponential in size(X), the number of simplices of Χ. Moreover, we prove that this is optimal: For every fixed d ≥ 2, we construct a family of simply connected simplicial complexes Χ such that for any simplicial map representing a generator of πd(Χ), the size of the triangulation of Sd on which the map is defined is exponential in size(X).

The concept of well group in a special but important case captures homological properties of the zero set of a continuous map $$f:K\rightarrow {\mathbb {R}}^n$$ f : K → R n on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within $$L_\infty $$ L ∞ distance r from f for a given $$r>0$$ r > 0 . The main drawback of the approach is that the computability of well groups was shown only when $$\dim K=n$$ dim K = n or $$n=1$$ n = 1 . Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set. For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of $${\mathbb {R}}^n$$ R n by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and $$\dim K<2n-2$$ dim K < 2 n - 2 , our approximation of the $$(\dim \ K-n)$$ ( dim K - n ) th well group is exact. For the second part, we find examples of maps $$f,f':K\rightarrow {\mathbb {R}}^n$$ f , f ′ : K → R n with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status.

The concept of well group in a special but important case captures homological properties of the zero set of a continuous map f from K to R^n on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within L_infty distance r from f for a given r > 0. The main drawback of the approach is that the computability of well groups was shown only when dim K = n or n = 1. Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set. For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of R^n by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and dim K < 2n-2, our approximation of the (dim K-n)th well group is exact. For the second part, we find examples of maps f, f' from K to R^n with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status.

We study the problem of robust satisfiability of systems of nonlinear equations, namely, whether for a given continuous function f : K → Rn on a finite simplicial complex K and α>0, it holds that each function g : K → Rn such that ║ g−f ║∞ ≤ α , has a root in K . Via a reduction to the extension problem of maps into a sphere, we particularly show that this problem is decidable in polynomial time for every fixed n , assuming dim K ≤ 2 n −3. This is a substantial extension of previous computational applications of topological degree and related concepts in numerical and interval analysis. Via a reverse reduction, we prove that the problem is undecidable when dim K ≥ 2 n −2, where the threshold comes from the stable range in homotopy theory. For the lucidity of our exposition, we focus on the setting when f is simplexwise linear. Such functions can approximate general continuous functions, and thus we get approximation schemes and undecidability of the robust satisfiability in other possible settings.

We study the problem of robust satisfiability of systems of nonlinear equations, namely, whether for a given continuous function f : K → R n on a finite simplicial complex K and α > 0, it holds that each function g : K → R n such that gf ∞ ≤ α, has a root in K. Via a reduction to the extension problem of maps into a sphere, we show that this problem is decidable if dim K ≤ 2n -3.This is a substantial extension of previous computational applications of topological degree and related concepts in numerical and interval analysis.Via a reverse reduction we prove that the problem is undecidable when dim K ≥ 2n -2, where the threshold comes from the stable range in homotopy theory.For the lucidity of our exposition, we focus on the setting when f is piecewise linear.Such functions can approximate general continuous functions, and thus we get approximation schemes and undecidability of the robust satisfiability in other possible settings.