Robust satisfiability of systems of equations
Franek, Peter
Krcál, Marek
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 dimK ≤ 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 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.
ACM
2015
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://research-explorer.app.ist.ac.at/record/1682
Franek P, Krcál M. Robust satisfiability of systems of equations. <i>Journal of the ACM</i>. 2015;62(4). doi:<a href="https://doi.org/10.1145/2751524">10.1145/2751524</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1145/2751524
info:eu-repo/semantics/openAccess