The algorithm designer versus nature: A game-theoretic approach to information-based complexity (Q1100895)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The algorithm designer versus nature: A game-theoretic approach to information-based complexity |
scientific article; zbMATH DE number 4045146
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The algorithm designer versus nature: A game-theoretic approach to information-based complexity |
scientific article; zbMATH DE number 4045146 |
Statements
The algorithm designer versus nature: A game-theoretic approach to information-based complexity (English)
0 references
1987
0 references
A new setting for analyzing problems in information-based complexity is formulated and discussed. By using concepts from two-person zero-sum game theory, a randomized setting results from defining the nth minimal radius as an infimum over ``mixed'' strategies of information operators and algorithms. After presenting an example, some general results are developed on the randomized radius and its relationship to average and worst case radii.
0 references
average case analysis
0 references
information-based complexity
0 references
two-person zero-sum game
0 references
randomized setting
0 references
