A gametheoretic classification of interactive complexity classes (1995)by J. Feigenbaum, D. Koller, and P. Shor
Abstract:
Gametheoretic characterizations of complexity classes have often proved useful in understanding the power and limitations of these classes. One wellknown example tells us that PSPACE can be characterized by twoperson, perfectinformation games in which the length of a played game is polynomial in the length of the description of the initial position [Chandra et al., JACM, 28 (1981)]. In this paper, we investigate the connection between game theory and interactive computation. We formalize the notion of a polynomially definable game system for the language L, which, informally, consists of two arbitrarily powerful players P1 and P2 and a polynomialtime referee V with a common input w. Player P1 claims that w in L, and player P2 claims that w not in L; the referee's job is to decide which of these two claims is true. In general, we wish to study the following question: What is the effect of varying the system's gametheoretic properties on the class of languages recognizable by polynomially definable game systems? There are many possible gametheoretic properties that we could investigate in this context. The focus of this paper is the question of what happens when one or both of the players P_1 and P_2 have imperfect information or imperfect recall. We use polynomially definable game systems to derive new characterizations of the complexity classes NEXP and coNEXP. We also derive partial results about other exponential complexity classes and isolate some intriguing open questions about the effects of imperfect information and imperfect recall. These results make use of recent work on complexitytheoretic aspects of games, e.g., [Koller et al., STOC '94] and [Lipton , STOC '94].
Download Information
J. Feigenbaum, D. Koller, and P. Shor (1995). "A gametheoretic classification of interactive complexity classes." Proceedings of the 10th Annual IEEE Conference on Structure in Complexity Theory (STRUCTURES) (pp. 227237).


Bibtex citation
@inproceedings{Feigenbaum+al:95,
title = {A gametheoretic classification of interactive complexity classes},
author = {J. Feigenbaum and D. Koller and P. Shor},
booktitle = {Proceedings of the 10th Annual IEEE Conference on Structure in Complexity Theory (STRUCTURES)},
address = {Minneapolis, Minnesota},
month = {June},
year = 1995,
pages = {227237},
}
full list
