No label defined (Q4226567)

This is an introduction to the theory of information-based complexity (IBC) that has been developed since the sixties by a continuously growing community of researchers around J. F. Traub, H. Woźniakowski et al.. IBC studies the computational complexity of ``problems for which information is partial, contaminated, and priced''. For a detailed presentation, see the monograph by \textit{J. F. Traub, G. W. Wasilkowski} and \textit{H. Woźniakowski} [Information-based complexity (1988; Zbl 0654.94004)]. The present text consists of expanded, updated versions of lectures given by Traub in 1993. It is written in an informal, motivating, and illustrating style. Part One (of the three) presents the background, aims, basic concepts, and some typical results of IBC. Numerical integration serves as a running example. First the univariate version is considered to motivate the worst-case estimation of deterministic algorithms. Then the multivariate task is used to discuss the ``curse of dimensionality'' and to introduce randomized algorithms as well as average-case estimations of deterministic ones. Part Two contains 12 chapters reporting or sketching the view and contributions of IBC to some special topics. In particular these are the following: very high-dimensional integration and mathematical finance; path integration; ill-posed problems; nonlinear problems; Turing machine model vs. real-number model of computation; do impossibility theorems from formal models limit scientific knowledge; linear programming; decision problems (verification); implementation testing for continuous problems; noisy information; value of information in computation; quantification of the values of mathematical hypotheses. Moreover, the open problems mentioned in the book are summarized, and the history of IBC is sketched. Part Three is a bibliography of more than 400 papers on IBC and related subjects. Thus, the present book both gives a well-readable overview of IBC as well as it offers a way of entering this field of research.