Plaskota L. Noisy Information and Computational Complexity

Издательство Cambridge University Press, 1996, -321 pp.In the modern world, the importance of information can hardly be overestimated. Information also plays a prominent role in scientific computations. A branch of computational complexity which deals with problems for which information is partial, noisy and priced is called information-based complexity.
In a number of information-based complexity books, the emphasis was on partial and exact information. In the present book, the emphasis is on noisy information. We consider deterministic and random noise. The analysis of noisy information leads to a variety of interesting new algorithms and complexity results.
The book presents a theory of computational complexity of continuous problems with noisy information. A number of applications is also given. It is based on results of many researchers in this area (including the results of the author) as well as new results not published elsewhere.Overview
Worst case setting
Average case setting
Worst-average case setting
Average-worst case setting
Asymptotic setting