---
_id: '1682'
abstract:
- lang: eng
  text: '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.'
article_number: '26'
article_processing_charge: No
arxiv: 1
author:
- first_name: Peter
  full_name: Franek, Peter
  last_name: Franek
- first_name: Marek
  full_name: Krcál, Marek
  id: 33E21118-F248-11E8-B48F-1D18A9856A87
  last_name: Krcál
citation:
  ama: 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>
  apa: Franek, P., &#38; Krcál, M. (2015). Robust satisfiability of systems of equations.
    <i>Journal of the ACM</i>. ACM. <a href="https://doi.org/10.1145/2751524">https://doi.org/10.1145/2751524</a>
  chicago: Franek, Peter, and Marek Krcál. “Robust Satisfiability of Systems of Equations.”
    <i>Journal of the ACM</i>. ACM, 2015. <a href="https://doi.org/10.1145/2751524">https://doi.org/10.1145/2751524</a>.
  ieee: P. Franek and M. Krcál, “Robust satisfiability of systems of equations,” <i>Journal
    of the ACM</i>, vol. 62, no. 4. ACM, 2015.
  ista: Franek P, Krcál M. 2015. Robust satisfiability of systems of equations. Journal
    of the ACM. 62(4), 26.
  mla: Franek, Peter, and Marek Krcál. “Robust Satisfiability of Systems of Equations.”
    <i>Journal of the ACM</i>, vol. 62, no. 4, 26, ACM, 2015, doi:<a href="https://doi.org/10.1145/2751524">10.1145/2751524</a>.
  short: P. Franek, M. Krcál, Journal of the ACM 62 (2015).
corr_author: '1'
date_created: 2018-12-11T11:53:27Z
date_published: 2015-08-01T00:00:00Z
date_updated: 2025-09-23T10:38:46Z
day: '01'
department:
- _id: UlWa
- _id: HeEd
doi: 10.1145/2751524
external_id:
  arxiv:
  - '1402.0858'
  isi:
  - '000361200500001'
intvolume: '        62'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1402.0858
month: '08'
oa: 1
oa_version: Preprint
publication: Journal of the ACM
publication_status: published
publisher: ACM
publist_id: '5466'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Robust satisfiability of systems of equations
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 62
year: '2015'
...