Games, complexity classes, and approximation algorithms.

From MaRDI portal





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.











This page was built for publication: Games, complexity classes, and approximation algorithms.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1126837)