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.
Recommendations
- Algorithmic Aspects of the Core of Combinatorial Optimization Games
- Playing Games with Approximation Algorithms
- scientific article; zbMATH DE number 5605130
- The approximation complexity of win-lose games
- Recent results and questions in combinatorial game complexities
- Approximation algorithms for unique games
- The complexity of solving stochastic games on graphs
- Mathematical Foundations of Computer Science 2005
- Computational complexity of Ehrenfeucht-Fraïssé games on finite structures
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)