## DIMACS TR: 95-21

## A Game-Theoretic Classification of Interactive Complexity Classe

### Authors: Joan Feigenbaum, Daphne Koller, Peter 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.,
Journal of the ACM, 28 (1981), pp.~114-133].
In this paper, we investigate the connection between game theory and
interactive computation. We formalize the notion of a "polynomially defineable
game system" for the language L, which, informally, consists of two
arbitrarily powerful players P1 and PP2 and a polynomial-time referee V with
a common input w. Player P1 claims that w is in L, and player P2 claims that
w is 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 P1 and P2 have imperfect information or
or imperfect recall.

We use polynomially definable game systems to derive new charactizations
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., Proc. 26th ACM Symposium on Theory of
computing, 1994, pp. 750-759] and [Newman, Information Processing Letters,
39 [1991), pp.~67-71.]

These results were presented in preliminary form at the 10th IEEE Structure
in Complexity Theory Conference, Minneapolis MN, June 1995.

Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-21.ps.gz

DIMACS Home Page