Computational complexity and feasibility of data processing and interval computations
The input data for data processing algorithms come from measurements and are hence not precise. We therefore need to estimate the accuracy of the results of data processing. It turns out that even for the simplest data processing algorithms, this problem is, in general, intractable. This book describes for what classes of problems interval computations (i.e. data processing with automatic results verification) are feasible, and when they are intractable.
This knowledge is important, e.g. for algorithm developers, because it will enable them to concentrate on the classes of problems for which general algorithms are possible.
What people are saying - Write a review
We haven't found any reviews in the usual places.
THE NOTIONS OF FEASIBILITY
IN THE GENERAL CASE
BASIC PROBLEM OF INTERVAL
23 other sections not shown
Other editions - View all
Computational Complexity and Feasibility of Data Processing and Interval ...
V. Kreinovich,A.V. Lakeyev,J. Rohn,P.T. Kahl
No preview available - 2010
6-narrow accuracy approximate arbitrary basic problem binary bounds chapter complexity and feasibility computational complexity computational problem computing the range conclude corresponding data processing definable real numbers denote describe desired e-approximately eigenvalues ellipsoid enclosure endpoints equal estimate exists a polynomial-time exponential f(xi feasible algorithm finite following problem formula F function f(x hence inequality input intervals integer interval computations interval linear systems interval matrix interval vector intractable Kreinovich linear equations linear functions matrix norm mean the following multi-interval non-negative NP-complete NP-hard NP-hard objective function optimization problem P-matrix PARTITION problem polynomial-time algorithm positive definite positive integer positive semi-definite possible values problem is NP-hard problem of computing problem of interval problem of solving Proof of Theorem prove quadratic function quadratic polynomials quantity rational coefficients rational function rational numbers regular result Rohn satisfy simplest solution intervals solvable stable symmetric matrix system of equations theorem is proven tuple variables