Geodesic
Games, complexity classes, and approximation algorithms.
Documenta mathematica, ICM Berlin 1998, Vol. III (1998), pp. 429-439.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

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.
Classification : 68Q15, 91A99
Keywords: perfect information, perfect recall 
@article{DOCMA_1998__S9__a36,
     author = {Feigenbaum, Joan},
     title = {Games, complexity classes, and approximation algorithms.},
     journal = {Documenta mathematica},
     pages = {429--439},
     publisher = {mathdoc},
     volume = {ICM Berlin 1998, Vol. III},
     year = {1998},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DOCMA_1998__S9__a36/}
}
TY  - JOUR
AU  - Feigenbaum, Joan
TI  - Games, complexity classes, and approximation algorithms.
JO  - Documenta mathematica
PY  - 1998
SP  - 429
EP  - 439
VL  - ICM Berlin 1998, Vol. III
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DOCMA_1998__S9__a36/
LA  - en
ID  - DOCMA_1998__S9__a36
ER  - 
%0 Journal Article
%A Feigenbaum, Joan
%T Games, complexity classes, and approximation algorithms.
%J Documenta mathematica
%D 1998
%P 429-439
%V ICM Berlin 1998, Vol. III
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DOCMA_1998__S9__a36/
%G en
%F DOCMA_1998__S9__a36
Feigenbaum, Joan. Games, complexity classes, and approximation algorithms.. Documenta mathematica, ICM Berlin 1998, Vol. III (1998), pp. 429-439. http://geodesic.mathdoc.fr/item/DOCMA_1998__S9__a36/