- Playing Savitch and Cooking games
- Book title
- Concurrency, compositionality, and correctness: essays in honor of Willem-Paul de Roever
- Pages (from-to)
- Number of pages
- Berlin: Springer
- Lecture Notes in Computer Science
- Volume | Edition (Serie)
- Document type
- Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
The complexity class PSPACE is one of the most robust concepts in contemporary computer science. Aside from the fact that space is invariant (for reasonable models at least) up to a constant factor, the class can be characterized in many alternative ways, involving parallel computation, logic problems like QBF, interactive computation models but also by means of games.
In the literature the connection between PSPACE and games is established as a consequence either of the PSPACE completeness of the QBF problem or as a consequence of the properties of the alternating computation model. Based on either of these starts one subsequently has investigated the PSPACE completeness of endgame analysis problems for various specific games.
The purpose of this note is to present a direct reduction of an arbitrary PSPACE problem into endgame analysis of a corresponding game. As a consequence we obtain an alternative proof of the 1970 Savitch theorem showing that PSPACE is closed under nondeterminism. Furthermore we reconsider the direct translation of endgame analysis of some game in QBF, in order to obtain a better understanding of the conditions on the game which enable this translation.
- go to publisher's site
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.