Book Review

The AMS does not provide abstracts of book reviews. You may download the entire review from the links below.

Full text of review: PDF This review is available free of charge.

Book Information:

Authors: J. F. Traub and A. G. Werschulz

Title: Complexity and information

Additional book information: Cambridge University Press, Cambridge, 1998, xii + 139 pp., ISBN ISBN 0-521-48506-1, $19.95, paperback

**[BSS]**L. Blum, M. Shub, and S. Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions, and universal machines,*Bull. Amer. Math. Soc.***21**(1989), 1-46. MR**90a:68022****[BCSS]**L. Blum, F. Cucker, F. Shub, and S. Smale,*Complexity and Real Computation*, Springer-Verlag, New York, 1998. MR**99a:68070****[CA]**D. Ceperley and B. Adler, Quantum Monte Carlo,*Science***231**(1986), 555-560.**[HS]**M. Hirsch and S. Smale, On algorithms for solving ,*Comm. Pure Appl*. Math.**2**(1979), 281-312. MR**80b:65061****[L]**S. Lloyd,*Measures of Complexity*, Department of Mechanical Engineering, Massachusetts Institute of Technology, Cambridge, MA.**[PW]**E. Packel and H. Wo niakowski, Recent developments ininformation-based complexity,*Bull. Amer. Math. Soc.***17**(1987), 9-36. MR**88h:65006****[PT]**E. Packel and J. Traub, Information-based complexity,*Nature***327**(1987), 29-33.**[S]**S. Smale, On the efficiency of algorithms of analysis,*Bull. Amer. Math. Soc*.**13**(1985), 87-121. MR**86m:65061****[SW]**I. Sloan and H. Wo niakowski, When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?*J. Complexity***14**(1998), 1-33. MR**99d:65384****[Tr]**J. Traub, On reality and models, in*Boundaries and Barriers: On the Limits to Scientific Knowledge*, Addison-Wesley, Reading, 1996, 238-254.**[TW]**J. Traub and H. Wo niakowski, Breaking intractability,*Scientific American***270**(1994), 102-107.**[T]**J. Traub,*Iterative methods for the solution of equations*, Prentice-Hall, Englewood Cliffs, N.J., 1964. MR**29:6607****[TWW]**J. Traub, G. Wasilkowski, and H. Wo niakowski,*Information-Based Complexity*, Academic Press, Boston, 1988. MR**90f:68085****[W]**A. Werschulz,*The Computational Complexity of Differential and Integral Equations: An Information-Based Approach*, Oxford University Press, New York, 1991. MR**93a:68061****[Wo]**H. Wo niakowski, Complexity of multivariate problems with applications to path integrals,*Z. Angew. Math. Mech.***3**(1996), 131-134.

Review Information:

Reviewer: Mark A. Kon

Affiliation: Boston University

Email: mkon@math.bu.edu

Journal: Bull. Amer. Math. Soc.

**37**(2000), 199-204

MSC (2000): Primary 65J05, 68Q01; Secondary 68Q05, 68Q15, 68Q25

DOI: https://doi.org/10.1090/S0273-0979-99-00859-9

Published electronically: December 21, 1999

Review copyright: © Copyright 2000 American Mathematical Society