The Complexity of Two Player Games of Incomplete Information.

摘要

We consider two-player games of incomplete information in which certain portions of positions are private to each player and cannot be viewed by the opponent. We provide asymptotically optimal decision algorithms for space bounded games. We present various games of incomplete information which are shown to be universal in the sense that they are the hardest of all reasonable games of incomplete information. The problem of determining the outcome of these universal games from a given initial position is shown to be complete in doubly-exponential time. We also define 'private alternating Turing machines' which are a new type of alternating Turing machines with certain private types. The space complexity S(n) of these machines is characterized in terms of the complexity of deterministic Turing machines, with time bounds doubly-exponential in S(n). We also consider blindfold games, which are restricted games in which the second player is not allowed to modify the common position. We provide asymptotically optimal decision algorithms for space bounded blindfold games.