On the complexity of rolling block and Alice mazes

Datum

2012

Betreuer/Gutachter

Weitere Beteiligte

Herausgeber

Zeitschriftentitel

ISSN der Zeitschrift

Bandtitel

Verlag

Zusammenfassung

We investigate the computational complexity of two maze problems, namely rolling block and Alice mazes. Simply speaking, in the former game one has to roll blocks through a maze, ending in a particular game situation, and in the latter one, one has to move tokens of variable speed through a maze following some prescribed directions. It turns out that when the number of blocks or the number of tokens is not restricted (unbounded), then the problem of solving such a maze becomes PSPACE-complete. Hardness is shown via a reduction from the nondeterministic constraint logic (NCL) of Demaine and Hearn to the problems in question. In this way we improve on a previous PSPACE-completeness result of Buchin and Buchin on rolling block mazes to best possible. Moreover, we also consider bounded variants of these maze games, i.e., when the number of blocks or tokens is bounded by a constant, and prove close relations to variants of graph reachability problems.

Beschreibung

Inhaltsverzeichnis

Anmerkungen

Erstpublikation in

Sammelband

URI der Erstpublikation

Forschungsdaten

Schriftenreihe

IFIG Research Report; 1202 / 2012

Erstpublikation in

Zitierform