Games, complexity classes, and approximation algorithms.
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.
scientific article; zbMATH DE number 1184381
scientific article