Complexity and Information

ISBN-13: 9780521485067 / Angielski / Miękka / 1998 / 154 str.

J. Traub; Arthur G. Werschulz; Luigi A. Radicati Di Brozolo

Opis

The twin themes of computational complexity and information pervade this book. It starts with an introduction to information-based complexity, that is, the computational complexity of continuous mathematical models. It then moves to a variety of topics, including breaking the curse of dimensionality, complexity of path integration, solvability of ill-posed problems, value of information in computation, assigning values to mathematical hypotheses, and mathematical finance. The style is informal, and the goal is motivation and insight. Precise statements and proofs can be found in the monographs and papers included in the comprehensive bibliography. The book will be essential reading for researchers in the many disciplines influenced by the computational complexity of continuous problems.

Recenzje

'Clearly written, filled with interesting examples, important theorems and tantalising conjectures, this is destined to be a classic.' New Scientist

Spis treści

Part I. Fundamentals: 1. Introduction; 2. Information-based complexity; 3. Breaking the curse of dimensionality; Part II. Some Interesting Topics: 4. Very high-dimensional integration and mathematical finance; 5. Complexity of path integration; 6. Are ill-posed problems solvable?; 7. Complexity of nonlinear problems; 8. What model of computation should be used by scientists?; 9. Do impossibility theorems from formal models limit scientific knowledge? 10. Complexity of linear programming; 11. Complexity of verification; 12. Complexity of implementation testing; 13. Noisy information; 14. Value of information in computation; 15. Assigning values to mathematical hypotheses; 16. Open problems; 17. A brief history of information-based complexity; Part III. References: 18. A guide to the literature; Bibliography; Subject index; Author index.