2014/02/04 by Peter Franek, Franek, Peter, Marek Krcal +1
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.1402.0858
arxiv created 2014/02/04 · arxiv updated 2014/02/05
We study the problem of robust satisfiability of systems of nonlinear equations, namely, whether for a given continuous function f: K→ℝn on a~finite simplicial complex K and α>0, it holds that each function g: K→ℝn 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 ≤ 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.