Robust satisfiability of systems of equations

DOI10.1145/2751524zbMATH Open1423.68208arXiv1402.0858OpenAlexW2058175730MaRDI QIDQ3177731FDOQ3177731

Authors: Peter Franek, Marek Krčál 

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Abstract: We study the problem of emph{robust satisfiability} of systems of nonlinear equations, namely, whether for a given continuous function $f:,Komathbb{R}^n$ on a~finite simplicial complex $K$ and $alpha>0$, it holds that each function $g:,Komathbb{R}^n$ such that $|g-f{|}_{i}nftyleqalpha$, 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 $dimKle2n-3$. This is a substantial extension of previous computational applications of emph{topological degree} and related concepts in numerical and interval analysis. Via a reverse reduction we prove that the problem is undecidable when $dimKge2n-2$, where the threshold comes from the emph{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.

Full work available at URL: https://arxiv.org/abs/1402.0858

Recommendations

• Robust satisfiability of systems of equations
• Satisfiability of systems of equations of real analytic functions is quasi-decidable
• Quasi-decidability of a fragment of the first-order theory of real numbers
• scientific article
• Solving equations and optimization problems with uncertainty

zbMATH Keywords

nonlinear equationssatisfiabilityundecidabilitytopological extension

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical computation of solutions to systems of equations (65H10) Functions of several variables (26B99)

Cited In (7)

• Computing simplicial representatives of homotopy group elements
• Robust feasibility of systems of quadratic equations using topological degree theory
• Computation of Cubical Steenrod Squares
• Satisfiability of systems of equations of real analytic functions is quasi-decidable
• Structured Systems of Nonlinear Equations
• Robustness of Solutions of Almost Every System of Equations
• Quasi-decidability of a fragment of the first-order theory of real numbers

This page was built for publication: Robust satisfiability of systems of equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177731)