Why intervals? Because if we allow other sets, tractable problems become intractable

DOI10.1023/A:1024475901686zbMATH Open0920.65030OpenAlexW141329415MaRDI QIDQ1276136FDOQ1276136

Authors: Monica Nogueira, Amarendra Nandigam 

Publication date: 9 September 1999

Published in: Reliable Computing (Search for Journal in Brave)

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

Recommendations

• Computation complexity of the range of a polynomial in several variables
• Range estimation is NP-hard for \({\varepsilon}^{2}\) accuracy and feasible for \({\varepsilon}^{2-\delta}\)
• Publication:4885382
• Mathematical Foundations of Computer Science 2003

zbMATH Keywords

complexityinterval arithmeticNP-hardmonotonic functionsinterval regionmultiinterval regionrange of a polynomial

Mathematics Subject Classification ID

Interval and finite arithmetic (65G30)

Cited In (8)

• Range estimation is NP-hard for \({\varepsilon}^{2}\) accuracy and feasible for \({\varepsilon}^{2-\delta}\)
• Computational complexity of optimization and crude range testing: A new approach motivated by fuzzy optimization
• Mathematical Foundations of Computer Science 2003
• The Complexity of Computing the Size of an Interval
• The complexity of computation and approximation of the \(t\)-ratio over one-dimensional interval data
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computation complexity of the range of a polynomial in several variables

This page was built for publication: Why intervals? Because if we allow other sets, tractable problems become intractable

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