Recent developments in information-based complexity
Edward W. Packel, Henryk Woźniakowski · Bulletin of the American Mathematical Society · 1987
IL Worst case setting 11 A. Problem formulation, information, and model of computation B. An integration example C. The radius and diameter of information D. Algorithms, complexity, and optimality III.Linear problems in a worst case setting 15 A. Definition and a basic lemma B. Adaptive vs. nonadaptive information C. The existence of linear optimal error algorithms D. e-Complexity and optimal information for linear problems IV.Average case setting 21 A. Historical summary B. Basic formulation C. Average radius of information D. Optimal error algorithms E.An integration example for the average case V. Linear problems in an average case setting 27 A. Radius of information and an optimal error algorithm B. Adaptive vs. nonadaptive information in the average case C. Average case e-complexity and optimal information for linear problems VI.Concluding Comments 32 References 34 I. Introduction.The notion of complexity, from both practical and theoretical standpoints, seems destined to be a major theme of research in both computer science and mathematics.As digital computers evolve, we find