Computational Complexity and Feasibility of Data Processing and Interval Computations

1. Front Matter

   Pages i-xii

   PDF

2. Informal Introduction: Data Processing, Interval Computations, and Computational Complexity

   • Vladik Kreinovich, Anatoly Lakeyev, Jiří Rohn, Patrick Kahl

   Pages 1-21

3. The Notions of Feasibility and NP-Hardness: Brief Introduction

   • Vladik Kreinovich, Anatoly Lakeyev, Jiří Rohn, Patrick Kahl

   Pages 23-39

4. In the General Case, the Basic Problem of Interval Computations is Intractable

   • Vladik Kreinovich, Anatoly Lakeyev, Jiří Rohn, Patrick Kahl

   Pages 41-51

5. Basic Problem of Interval Computations for Polynomials of a Fixed Number of Variables

   • Vladik Kreinovich, Anatoly Lakeyev, Jiří Rohn, Patrick Kahl

   Pages 53-70

6. Basic Problem of Interval Computations for Polynomials of Fixed Order

   • Vladik Kreinovich, Anatoly Lakeyev, Jiří Rohn, Patrick Kahl

   Pages 71-78

7. Basic Problem of Interval Computations for Polynomials with Bounded Coefficients

   • Vladik Kreinovich, Anatoly Lakeyev, Jiří Rohn, Patrick Kahl

   Pages 79-82

8. Fixed Data Processing Algorithms, Varying Data: Still NP-Hard

   • Vladik Kreinovich, Anatoly Lakeyev, Jiří Rohn, Patrick Kahl

   Pages 83-84

9. Fixed Data, Varying Data Processing Algorithms: Still Intractable

   • Vladik Kreinovich, Anatoly Lakeyev, Jiří Rohn, Patrick Kahl

   Pages 85-86

10. What if We only Allow some Arithmetic Operations in Data Processing?

    • Vladik Kreinovich, Anatoly Lakeyev, Jiří Rohn, Patrick Kahl

    Pages 87-90

11. For Fractionally-Linear Functions, a Feasible Algorithm Solves the Basic Problem of Interval Computations

    • Vladik Kreinovich, Anatoly Lakeyev, Jiří Rohn, Patrick Kahl

    Pages 91-98

12. Solving Interval Linear Systems is NP-Hard

    • Vladik Kreinovich, Anatoly Lakeyev, Jiří Rohn, Patrick Kahl

    Pages 99-110

13. Interval Linear Systems: Search for Feasible Classes

    • Vladik Kreinovich, Anatoly Lakeyev, Jiří Rohn, Patrick Kahl

    Pages 111-142

14. Physical Corollary: Prediction is not Always Possible, Even for Linear Systems with Known Dynamics

    • Vladik Kreinovich, Anatoly Lakeyev, Jiří Rohn, Patrick Kahl

    Pages 143-151

15. Engineering Corollary: Signal Processing is NP-Hard

    • Vladik Kreinovich, Anatoly Lakeyev, Jiří Rohn, Patrick Kahl

    Pages 153-158

16. Bright Sides of NP-Hardness of Interval Computations I: NP-Hard Means That Good Interval Heuristics can Solve other Hard Problems

    • Vladik Kreinovich, Anatoly Lakeyev, Jiří Rohn, Patrick Kahl

    Pages 159-160

17. If Input Intervals are Narrow Enough, Then Interval Computations are Almost Always Easy

    • Vladik Kreinovich, Anatoly Lakeyev, Jiří Rohn, Patrick Kahl

    Pages 161-172

18. Optimization — a First Example of a Numerical Problem in which Interval Methods are used: Computational Complexity and Feasibility

    • Vladik Kreinovich, Anatoly Lakeyev, Jiří Rohn, Patrick Kahl

    Pages 173-196

19. Solving Systems of Equations

    • Vladik Kreinovich, Anatoly Lakeyev, Jiří Rohn, Patrick Kahl

    Pages 197-205

20. Approximation of Interval Functions

    • Vladik Kreinovich, Anatoly Lakeyev, Jiří Rohn, Patrick Kahl

    Pages 207-217

Targeted audience • Specialists in numerical computations, especially in numerical optimiza­ tion, who are interested in designing algorithms with automatie result ver­ ification, and who would therefore be interested in knowing how general their algorithms caIi in principle be. • Mathematicians and computer scientists who are interested in the theory 0/ computing and computational complexity, especially computational com­ plexity of numerical computations. • Students in applied mathematics and computer science who are interested in computational complexity of different numerical methods and in learning general techniques for estimating this computational complexity. The book is written with all explanations and definitions added, so that it can be used as a graduate level textbook. What this book .is about Data processing. In many real-life situations, we are interested in the value of a physical quantity y that is diflicult (or even impossible) to measure directly. For example, it is impossible to directly measure the amount of oil in an oil field or a distance to a star. Since we cannot measure such quantities directly, we measure them indirectly, by measuring some other quantities Xi and using the known relation between y and Xi'S to reconstruct y. The algorithm that transforms the results Xi of measuring Xi into an estimate fj for y is called data processing.

• Approximation
• Signal
• Variable
• algorithm
• algorithms
• complexity
• optimization
• verification

`The book is very well organized. The book is readable, very detailed, and intelligible. Moreover, it is exciting and gripping because the reader is often surprised by unexpected results. Everyone who is interested in modern aspects of numerical computation will enjoy reading this interesting and informative work. The book is a must for everyone who is doing research in this field.'
Mathematical Reviews, 98m

• University of Texas at El Paso, USA

  Vladik Kreinovich

• Computing Center, Russian Academy of Sciences, Irkutsk, Russia

  Anatoly Lakeyev

• Charles University and Academy of Sciences, Prague, Czech Republic

  Jiří Rohn

• IBM, Tucson, USA

  Patrick Kahl

Policies and ethics