Range estimation is NP-hard for ^2 accuracy and feasible for ^2-

DOI10.1023/A:1021368627321MaRDI QIDQ1869604zbMATH OpenOpenAlexFDO

Authors Vladik Kreinovich

Publication date 28 April 2003

Published in Reliable Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1021368627321

zbMATH Keywords

algorithmcomplexityNP-hardasymptotic range estimationinterval compulations

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Interval and finite arithmetic (65G30)

Recommendations

• Computation complexity of the range of a polynomial in several variables
• Why intervals? Because if we allow other sets, tractable problems become intractable
• Publication:4885382
• Error estimation for indirect measurements: Interval computation problem is (slightly) harder than a similar probabilistic computational problem
• On a refined analysis of some problems in interval arithmetic using real number complexity theory

Cited in

(8)

• Computation complexity of the range of a polynomial in several variables
• scientific article; zbMATH DE number 903768 (Why is no real title available?)
• Computational complexity of optimization and crude range testing: A new approach motivated by fuzzy optimization
• Towards a combination of interval and ellipsoid uncertainty
• Mathematical Foundations of Computer Science 2003
• On a refined analysis of some problems in interval arithmetic using real number complexity theory
• Importance sampling for estimating expected values: a heuristic approach for NP-hard interval problems
• The complexity of computation and approximation of the \(t\)-ratio over one-dimensional interval data

This page was built for publication: Range estimation is NP-hard for \({\varepsilon}^{2}\) accuracy and feasible for \({\varepsilon}^{2-\delta}\)

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