Robust Satisfiability of Systems of Equations

0427751 - ÚI 2015 RIV US eng C - Conference Paper (international conference)
Franek, Peter - Krčál, M.
Robust Satisfiability of Systems of Equations.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia: SIAM, 2014 - (Chekuri, C.), s. 193-203. ISBN 978-1-61197-338-9.
[SODA 2014. Annual ACM-SIAM Symposium on Discrete Algorithms /25./. Portland (US), 05.01.2014-07.01.2014]
R&D Projects: GA ČR GBP202/12/G061
Grant - others:GA MŠk(CZ) LL1201
Institutional support: RVO:67985807
Keywords : robust satisfiability * nonlinear system * undecidability * topological extension problem
Subject RIV: IN - Informatics, Computer Science

We study the problem of robust satisfiability of systems of nonlinear equations, namely, whether for a given continuous function f: K \to Rn on a finite simplicial complex K and alpha>0, it holds that each function g:K \to Rn such that ||g-f|| <= alpha, 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.
Permanent Link: http://hdl.handle.net/11104/0233248