Author | Kreinovich, Vladik. author |
---|---|
Title | Computational Complexity and Feasibility of Data Processing and Interval Computations [electronic resource] / by Vladik Kreinovich, Anatoly Lakeyev, Jiลรญ Rohn, Patrick Kahl |
Imprint | Boston, MA : Springer US : Imprint: Springer, 1998 |
Connect to | http://dx.doi.org/10.1007/978-1-4757-2793-7 |
Descript | XII, 459 p. online resource |
1 Informal Introduction: Data Processing, Interval Computations, and Computational Complexity -- 2 The Notions of Feasibility and NP-Hardness: Brief Introduction -- 3 In the General Case, the Basic Problem of Interval Computations is Intractable -- 4 Basic Problem of Interval Computations for Polynomials of a Fixed Number of Variables -- 5 Basic Problem of Interval Computations for Polynomials of Fixed Order -- 6 Basic Problem of Interval Computations for Polynomials with Bounded Coefficients -- 7 Fixed Data Processing Algorithms, Varying Data: Still NP-Hard -- 8 Fixed Data, Varying Data Processing Algorithms: Still Intractable -- 9 What if We only Allow some Arithmetic Operations in Data Processing? -- 10 For Fractionally-Linear Functions, a Feasible Algorithm Solves the Basic Problem of Interval Computations -- 11 Solving Interval Linear Systems is NP-Hard -- 12 Interval Linear Systems: Search for Feasible Classes -- 13 Physical Corollary: Prediction is not Always Possible, Even for Linear Systems with Known Dynamics -- 14 Engineering Corollary: Signal Processing is NP-Hard -- 15 Bright Sides of NP-Hardness of Interval Computations I: NP-Hard Means That Good Interval Heuristics can Solve other Hard Problems -- 16 If Input Intervals are Narrow Enough, Then Interval Computations are Almost Always Easy -- 17 Optimization โ a First Example of a Numerical Problem in which Interval Methods are used: Computational Complexity and Feasibility -- 18 Solving Systems of Equations -- 19 Approximation of Interval Functions -- 20 Solving Differential Equations -- 21 Properties of Interval Matrices I: Main Results -- 22 Properties of Interval Matrices II: Proofs and Auxiliary Results -- 23 Non-Interval Uncertainty I: Ellipsoid Uncertainty and its Generalizations -- 24 Non-Interval Uncertainty II: Multi-Intervals and Their Generalizations -- 25 What if Quantities are Discrete? -- 26 Error Estimation for Indirect Measurements: Interval Computation Problem is (Slightly) Harder than a Similar Probabilistic Computational Problem -- A In Case of Interval (Or More General) Uncertainty, no Algorithm can Choose the Simplest Representative -- B Error Estimation for Indirect Measurements: Case of Approximately Known Functions -- C From Interval Computations to Modal Mathematics -- D Beyond NP: Two Roots Good, one Root Better -- E Does โNP-HardโReally Mean โIntractableโ? -- F Bright Sides of NP-Hardness of Interval Computations II: Freedom of Will? -- G The Worse, The Better: Paradoxical Computational Complexity of Interval Computations and Data Processing -- References