Author(s):

Franek, Peter; Krčál, Marek

Article Title: 
Robust satisfiability of systems of equations

Affiliation 
IST Austria 
Abstract: 
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.

Keywords: 
satisfiability; Nonlinear equations; Topological extension; Undecidability

Journal Title:

Journal of the ACM

Volume: 
62

Issue 
4

ISSN:

00045411

Publisher:

ACM

Date Published:

20150801

Start Page: 
Article number: 26

Sponsor: 
This research was supported by the Center of Excellence – Institute for Theoretical Computer Science, Prague (project P202/12/G061 of GA ˇ CR), by the Project LL1201 ERCCZ CORES and by institutional support RVO:67985807.

URL: 

DOI: 
10.1145/2751524

Open access: 
yes (repository) 