PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
By R. Hearn, Erik D. Demaine. Theoretical Computer Science, 2002
330 citations recorded by the source corpus.
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 [Theoret. Comput. Sci. 270(1-2) (2002) 8951.We illustrate the importance of our model of computation by giving simple reductions to show that several 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 [Theoret. Comput. Sci. 270(1-2) (2002) 895], of which we also give a simpler proof. We also greatly strengthen the conditions for the PSPACE-hardness of the Warehouseman's Problem [Int. J. Robot. Res. 3(4) (1984) 76], a classic motion-planning problem. Finally, we strengthen the existing result that the pushing-blocks puzzle Sokoban is PSPACE-complete [In: Proc. Internat. Conf. on Fun with Algorithms, Elba, Italy, June 1998, pp. 65-76.], by showing that it is PSPACE-complete even if no barriers are allowed.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design
View Paper: https://www.semanticscholar.org/paper/381512ebe897d7a4530d7a7d97e40e5fd4fba1b9
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Computational Theory and Mathematics
In Computer Graphics and Computer-Aided Design
Citations in the corpus
- Mixing graph colourings (2007, methodology): “The authors of [30] claim without proof that every NCL graph is reducible in logarithmic space to an equivalent (in terms of the given decision problems) And/Or constraint graph—this is a graph composed exclusively of And and Or vertices.”
- Finding Optimal Solutions to Cooperative Pathfinding Problems (2010, background): “All rights reserved. and Sharir 1984; Hearn and Demaine 2005), and the standard admissible algorithm for cooperative pathfinding problems has a branching factor that is exponential in the number of agents (Silver 2005).”