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].