Computation complexity of the range of a polynomial in several variables

DOI10.1007/BF01070595zbMATH Open0608.68028MaRDI QIDQ3747719FDOQ3747719

Authors: A. A. Gaganov 

Publication date: 1985

Published in: Cybernetics (Search for Journal in Brave)

Recommendations

• Range estimation is NP-hard for \({\varepsilon}^{2}\) accuracy and feasible for \({\varepsilon}^{2-\delta}\)
• Why intervals? Because if we allow other sets, tractable problems become intractable
• Publication:4885382
• scientific article; zbMATH DE number 869739
• scientific article; zbMATH DE number 440791

zbMATH Keywords

interval analysisNP-hardrelative accuracyabsolute accuracyinterval of values of a polynomialmulti-variable polynomial

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Interval and finite arithmetic (65G30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On computing the range of a rational function of n variables over a bounded region

Cited In (12)

• On the complexity of the computation of certain classes of polynomials of several variables
• A characterization of NP within interval-valued computing
• Range estimation is NP-hard for \({\varepsilon}^{2}\) accuracy and feasible for \({\varepsilon}^{2-\delta}\)
• Simulation of discrete linear time-invariant fuzzy dynamic systems
• A combined method for enclosing all solutions of nonlinear systems of polynomial equations
• Polytope-based computation of polynomial ranges
• Mathematical Foundations of Computer Science 2003
• On a refined analysis of some problems in interval arithmetic using real number complexity theory
• A bright side of NP-hardness of interval computations: Interval heuristics applied to NP-problems
• The complexity of computation and approximation of the \(t\)-ratio over one-dimensional interval data
• Title not available (Why is that?)
• Fuzzy constraint networks for signal pattern recognition

This page was built for publication: Computation complexity of the range of a polynomial in several variables

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