No label defined (Q4040428)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 193625
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 193625 |
Statements
5 June 1993
0 references
information-based complexity theory
0 references
cost of an algorithm
0 references
worst case
0 references
average case
0 references
0.840494692325592
0 references
0.8033462166786194
0 references
The book is about information-based complexity theory - in contrast to computational complexity theory. The central notion here is that of information - roughly meaning the amount of knowledge about the computational problem to be solved. In practical applications, information about problems is either partial or noisy. For such problems, only approximate solutions are possible. This book constitutes a very general theory to deal with this situation. The gaining of information about a problem in question is considered to be priced, leading to the notion of cost of an algorithm. The cost and the approximation error of algorithms can be variously defined, leading to 3 major different settings studied in this book: the worst case, the average case, and the probabilistic setting.
0 references
