Paper by Erik D. Demaine

Reference:: Robert A. Hearn and Erik D. Demaine, “The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications”, in Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP 2002), Lecture Notes in Computer Science, volume 2380, Malaga, Spain, July 8–13, 2002, pages 401–413.
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 [2].
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 (1x2 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 [2], of which we also give a simpler proof. Finally, we strengthen the existing result that the pushing-blocks puzzle Sokoban is PSPACE-complete [1], by showing that it is PSPACE-complete even if no barriers are allowed.
Comments:: This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/2380/23800401.pdf.
Updates:: Ivars Peterson wrote an article describing these results, “Logic in the Blocks”, Science News 162(7):106-108, August 17, 2002.
Copyright:: The paper is \copyright Springer-Verlag.
Length:: The paper is 12 pages.
Availability:: The paper is available in PostScript (5986k), gzipped PostScript (3316k), and PDF (279k).; See information on file formats.; [Google Scholar search]
Related papers:: NCL_TCS (PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation)