Paper by Erik D. Demaine

Robert A. Hearn and Erik D. Demaine, “PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation”, Theoretical Computer Science, volume 343, number 1–2, October 2005, pages 72–96. Special issue ``Game Theory Meets Theoretical Computer Science''.

We present a nondeterministic model of computation based on reversing edge directions in weighted directed graphs with minimum in-flow constraints on vertices. Deciding whether this simple graph model can be manipulated in order to reverse the direction of a particular edge is shown to be PSPACE-complete by a reduction from Quantified Boolean Formulas. We prove this result in a variety of special cases including planar graphs and highly restricted vertex configurations, some of which correspond to a kind of passive constraint logic. Our framework is inspired by (and indeed a generalization of) the “Generalized Rush Hour Logic” developed by Flake and Baum [4].

We illustrate the importance of our model of computation by giving simple reductions to show that multiple motion-planning problems are PSPACE-hard. Our main result along these lines is that classic unrestricted sliding-block puzzles are PSPACE-hard, even if the pieces are restricted to be all dominoes (1 × 2 blocks) and the goal is simply to move a particular piece. No prior complexity results were known about these puzzles. This result can be seen as a strengthening of the existing result that the restricted Rush HourTM puzzles are PSPACE-complete [4], of which we also give a simpler proof. We also greatly strengthen the conditions for the PSPACE-hardness of the Warehouseman's Problem [6], a classic motion-planning problem. Finally, we strengthen the existing result that the pushing-blocks puzzle Sokoban is PSPACE-complete [2], by showing that it is PSPACE-complete even if no barriers are allowed.

This paper is also available as arXiv:cs.CC/0205005 of the Computing Research Repository (CoRR), and from ScienceDirect.

Ivars Peterson wrote an article describing these results, “Logic in the Blocks”, Science News 162(7):106-108, August 17, 2002.

The paper is available in PDF (372k).
See information on file formats.
[Google Scholar search]

Related papers:
NCL_ICALP2002 (The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications)
CL_Complexity2008 (Constraint Logic: A Uniform Framework for Modeling Computation as Games)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated July 7, 2020 by Erik Demaine.