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

DOI10.1023/A:1021368627321zbMATH Open1071.65069OpenAlexW33079676MaRDI QIDQ1869604FDOQ1869604

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

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

zbMATH Keywords

algorithmcomplexityNP-hardasymptotic range estimationinterval compulations

Mathematics Subject Classification ID

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

Cited In (8)

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

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)