Robust Satisfiability of Systems of Equations
Peter Franek, Marek Krčál · 2013
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.