Paper by Erik D. Demaine

Reference:

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”.

Abstract:

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 Hour^TM 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.

Comments:

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

Updates:

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

Availability:

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)