Playing Savitch and Cooking games

Authors
Publication date 2010
Host editors
  • D. Dams
  • U. Hannemann
  • M. Steffen
Book title Concurrency, compositionality, and correctness: essays in honor of Willem-Paul de Roever
ISBN
  • 9783642115110
Series Lecture Notes in Computer Science, 5930
Pages (from-to) 10-21
Number of pages 375
Publisher Berlin: Springer
Organisations
  • Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
Abstract
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.
Document type Chapter
Language English
Published at https://doi.org/10.1007/978-3-642-11512-7_2
Permalink to this page
Back