Games, complexity classes, and approximation algorithms. (Q1126837)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Games, complexity classes, and approximation algorithms. |
scientific article |
Statements
Games, complexity classes, and approximation algorithms. (English)
0 references
5 August 1998
0 references
Summary: We survey recent results about game-theoretic characterizations of computational complexity classes. We also show how these results are used to prove that certain natural optimization functions are as hard to approximate closely as they are to compute exactly.
0 references
perfect information
0 references
perfect recall
0 references
