Games, complexity classes, and approximation algorithms. (Q1126837)
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: Games, complexity classes, and approximation algorithms. |
scientific article; zbMATH DE number 1184381
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Games, complexity classes, and approximation algorithms. |
scientific article; zbMATH DE number 1184381 |
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
0.9032393
0 references
0.8922175
0 references
0.88085777
0 references
0.8771619
0 references
0 references
0.87204427
0 references
0.87141275
0 references
