Games, complexity classes, and approximation algorithms.
type: Item
instance of: scholarly article
title: Games, complexity classes, and approximation algorithms.
zbMATH Open document ID: 1034.68521
author: Joan Feigenbaum
published in: Documenta Mathematica
publication date: 1998-08-05T00:00:00Z
full work available at URL: https://eudml.org/doc/222677
full work available at URL: Feigenbaum.MAN.html
review text: 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.
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 91A99
zbMATH DE Number: 1184381
zbMATH Keywords: perfect information
zbMATH Keywords: perfect recall
MaRDI profile type: Publication
Recommended article: Algorithmic Aspects of the Core of Combinatorial Optimization Games
Recommended article: Playing Games with Approximation Algorithms
Recommended article: Q3396628
Recommended article: Q2934593
Recommended article: Recent results and questions in combinatorial game complexities
Recommended article: Q3002794
Recommended article: The Complexity of Solving Stochastic Games on Graphs
Recommended article: Mathematical Foundations of Computer Science 2005
Recommended article: Q4263796
description: scientific article; zbMATH DE number 1184381