Title: Games, Complexity Classes, and Approximation Algorithms

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.

1991 Mathematics Subject Classification: 68Q15

Keywords and Phrases: Games, Complexity, Approximation Algorithms, Perfect Information, Perfect Recall

Full text: dvi.gz 21 k, dvi 49 k, ps.gz 61 k.

Home Page of DOCUMENTA MATHEMATICA