Computational Models of Games
Anne Condon · Medical Entomology and Zoology · 1989
Because games and game-like phenomena occur naturally in a computational setting, it is natural to formulate many problems in Computer Science in terms of games. In order to understand their complexity, various models of computation have been developed which reflect the game-like properties of such problems. These models include the alternating Turing machines of Chandra, Kozen, and Stockmeyer (CKS81), the games against nature of Papadimitriou (PAP83), the Arthur-Merlin games of Babai (BAB85), and the interactive proof systems of Goldwasser, Micali, and Rackoff (GMR85). We unify and extend the work on these game-like models of computation. We define a new computational model of two person games, called a probabilistic game automaton. Three important features of games are included in the definition: randomness, secrecy and limited power for the players. Probabilistic game automata are defined as language acceptors, where the input is accessible to both players. We prove a number of results on the complexity of some classes of languages accepted by special types of game automata encompassed by our model. To state these results precisely, we use a consistent notation throughout the dissertation. Some of these results are summarized here. In our notation, we let UP, (UC) denote the class of two-person games with unbounded two-sided error and partial information (complete information), where one player plays randomly. Hence, UC refers to games against known nature and UP refers to games against unknown nature. We show that ATIME(poly(n)) = UC--TIME(poly(n)) = UP--TIME(poly(n)) and ASPACE(poly(n)) = UC--SPACE(poly(n)) $\subseteq$ UP--SPACE(log((n))), where ATIME and ASPACE refer to alternating Turing machines and poly(n) is any polynomial function of n. Here and in the results below we assume that the space and time bounds are deterministically constructible. We also prove a number of new results on the power of the space bounded analogues of Arthur-Merlin games and interactive proof systems. We denote these by BC and BP respectively, for probabilistic games with bounded error with complete and partial information, respectively. Our main results are that ASPACE(poly(n)) = BC--SPACE(poly(n)) $\subseteq$ BP--SPACE(log(n)). As a consequence, any language recognizable in deterministic exponential time has an interactive proof which uses only logarithmic space.