Estimating the range of a polynomial on an interval with relative accuracy is NP-hard for 1 and feasible for > 1

MaRDI QIDQ6897006zbMATH OpenFDO

Authors Vladik Kreinovich, Sergey P. Shary

Publication date 20 November 2025

Published in Sibirskiĭ Zhurnal Vychislitel'noĭ Matematiki (Search for Journal in Brave)

zbMATH Keywords

feasible problemGaganov theoremNP-hard problemrange of a polynomial

Mathematics Subject Classification ID

Interval and finite arithmetic (65G30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Symbolic computation and algebraic computation (68W30)

Cites work

• Computation complexity of the range of a polynomial in several variables
• Computational complexity and feasibility of data processing and interval computations
• scientific article; zbMATH DE number 1595639 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• Interval analysis and automatic result verification
• Interval methods for solving nonlinear constraint satisfaction, optimization and similar problems. From inequalities systems to game solutions
• Introduction to Interval Analysis
• Measurement Errors and Uncertainties

This page was built for publication: Estimating the range of a polynomial on an interval with relative accuracy \(\varepsilon\) is NP-hard for \(\varepsilon\leqslant 1\) and feasible for \(\varepsilon> 1\)

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