Deciding accurate evaluability of real polynomials
Consider finite arithmetic computation trees with exact real inputs $x \in \mathbb{R}^n$ and no constant inputs. Each arithmetic node applies addition, subtraction or multiplication to two available quantities $a, b$ and returns $(a \circ b)(1 + \delta_j)$; each operation has its own arbitrary error $\delta_j$, so equal operands need not produce equal errors. Negation and comparisons ($<$, $=$, $>$) of available quantities are exact, branching is allowed, and computed values may be stored and reused: the tree describes control flow, not a formula that recomputes each occurrence of a subexpression. Number the rounded nodes of a tree $P$ by $1, \dots, N(P)$ and write $P(x, \delta)$ for its output, errors on unused branches being ignored. For $p \in \mathbb{Z}[x_1, \dots, x_n]$ with $p(0) = 0$, call $P$ accurate for $p$ if $P(x, 0) = p(x)$ and $$\forall \eta \in (0, 1)\ \exists u \in (0, 1)\ \forall x \in \mathbb{R}^n\ \forall \delta \in [-u, u]^{N(P)}: \quad |P(x, \delta) - p(x)| \le \eta\, |p(x)|.$$ The same tree must serve every $\eta$, and $u$ may depend on $p$, $P$ and $\eta$ but not on $x$; in particular, an accurate tree is exact at the zeros of $p$.
This is, for real inputs, the traditional arithmetic of Demmel, Dumitriu and Holtz, who seek a decision procedure that either produces an accurate algorithm for a given polynomial or shows that none exists. Whether a given tree is accurate is decidable by Tarski's method, as Demmel, Dumitriu, Holtz and Koev note. Demmel, Dumitriu and Holtz showed that if $p$ has an accurate algorithm on $\mathbb{R}^n$, then its zero set is allowable, that is, a union of intersections of hyperplanes $x_i = 0$, $x_i + x_j = 0$ and $x_i - x_j = 0$; so $x_1 + x_2 + x_3$ has none. For complex inputs and integer polynomials with zero constant term, they showed that this condition is also sufficient on $\mathbb{C}^n$.
Problem. Is there a Turing algorithm that, given the list of integer coefficients of any such $p$, always halts and decides whether an accurate tree for $p$ exists? No bound on its running time is prescribed.
Source: Stated by OpenProblemsInNLA, after Demmel, Dumitriu and Holtz (2006), §1–2 (first posted as arXiv:math/0508350, 2005), who seek a decision procedure for accurate evaluability, and Demmel, Dumitriu, Holtz and Koev (2008), §3.1 and §3.3.7; here for integer polynomials on ℝⁿ in their traditional arithmetic without constants, with Turing decidability asked.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- AG, LO
- Keywords
- decision procedures, OpenProblemsInNLA, polynomial evaluation, rounding errors
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@incollection{demmel2006,
author = {Demmel, James and Dumitriu, Ioana and Holtz, Olga},
title = {Toward accurate polynomial evaluation in rounded arithmetic},
booktitle = {Foundations of Computational Mathematics, Santander 2005},
editor = {Pardo, Luis M. and Pinkus, Allan and S{\"u}li, Endre and Todd, Michael J.},
series = {London Math. Soc. Lecture Note Ser.},
volume = {331},
publisher = {Cambridge Univ. Press},
address = {Cambridge},
year = {2006},
pages = {36--105},
doi = {10.1017/CBO9780511721571.003},
eprint = {math/0508350},
archivePrefix = {arXiv},
}
@article{demmel2008,
author = {Demmel, James and Dumitriu, Ioana and Holtz, Olga and Koev, Plamen},
title = {Accurate and efficient expression evaluation and linear algebra},
journal = {Acta Numer.},
volume = {17},
year = {2008},
pages = {87--145},
doi = {10.1017/S0962492906350015},
eprint = {0712.4027},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-aa01,
author = {Townsend, Alex},
title = {{AA-01}: Deciding accurate evaluability of real polynomials},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/arithmetic-and-complexity/AA-01/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
For integer polynomials $p$ with $p(0) = 0$, the paper characterizes the existence of an accurate evaluation algorithm on $\mathbb{R}^n$ in the model of finite computation trees with exact real inputs, independently rounded addition, subtraction and multiplication, exact negation and comparisons, branching, stored values and no constants. The characterization uses the finitely many regions determined by input signs and the …
The manuscript gives a finite criterion for the existence of accurate evaluation algorithms for real polynomials in the constant-free, independently rounded arithmetic model. For each ordering of the input magnitudes and each choice of their signs, the inputs are written as signed cumulative sums of nonnegative gaps and the polynomial is expanded in these gaps; the criterion requires that the …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Needs verification → Solution claimed | clemens-admin | Listed with the record of its solution, unreviewed. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00255, "Deciding accurate evaluability of real polynomials", clopen.solutions.