COMPLEXITY AND INFORMATION
J.F. TRAUB
Department of Computer Science, Columbia University
A.G. WERSCHULZ
Department of Computer and Information Science, Fordham University
Department of Computer Science, Columbia University
Cambridge University Press
Simultaneous publication in hard and soft cover as part of the series Lezioni Lincee, Accademia Nazionale dei Lincei.
|
|
|
||
|
|
|
||
|
|
|
This monograph is a greatly expanded and updated version of the series of lectures that Joseph Traub presented by invitation of the Academia Nazionale dei Lincei at the Scuola Normale Superiore in Pisa.
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 useful to researchers in the many disciplines influenced by the computational complexity of continuous problems.
"This short volume packs so much information into so small a space that it stretches the imagination as to know how the authors did it. Clearly written, filled with interesting examples, important theorems and tantalizing conjectures, this book should be taken as holiday reading by everyone concerned with using a computer to solve real problems. It's destined to be a classic."
New Scientist
"The exposition is straightforward and clear, with well-chosen diagrams to smooth the way...The broad expanse between technical and general themes may be one of the more challenging and appealing aspects of the book...This book provides worthwhile evidence that IBC (information based complexity) is an important, albeit highly specialized, approach to understanding and applying information in modeling the complexity of a variety of mathematically formulated problems."
Complexity
"...gives a good grounding in the essential issues of complexity and information. For an overview of the larger issues, this small book is excellent."
Bulletin of the AMS
"Really a jewel...written with loving care and in an elegant style."
Institute of Discrete Mathematics
"Highly recommended."
Choice
"Anyone interested in numerical analysis and scientific computing can profit from the book and its many insights."
Siam Review
