My home page
Biography
Research
Publications
My group
Courses
Professional activities
FAQ
Personal
Papers

Daphne Koller Publications

A game-theoretic classification of interactive complexity classes (1995)

by J. Feigenbaum, D. Koller, and P. Shor


Abstract: Game-theoretic characterizations of complexity classes have often proved useful in understanding the power and limitations of these classes. One well-known example tells us that PSPACE can be characterized by two-person, perfect-information 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 polynomial-time 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 game-theoretic properties on the class of languages recognizable by polynomially definable game systems?
There are many possible game-theoretic 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 complexity-theoretic 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 game-theoretic classification of interactive complexity classes." Proceedings of the 10th Annual IEEE Conference on Structure in Complexity Theory (STRUCTURES) (pp. 227-237). pdf ps.gz

Bibtex citation

@inproceedings{Feigenbaum+al:95,
  title = {A game-theoretic 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 = {227--237},
}

full list
Click to go to robotics Click to go to theory Click to go to CS Stanford Click to go to Stanford's Webpage
home | biography | research | papers | my group
courses | professional activities | FAQ | personal