Robust satisfiability of systems of equations

DOI10.1145/2751524MaRDI QIDQ3177731zbMATHOpenAlexFDO

Authors Peter Franek, Marek Krčál

Publication date 2 August 2018

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

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

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)

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.

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; zbMATH DE number 4213455
• Solving equations and optimization problems with uncertainty

Cited in

(9)

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

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)