Computer Science – Computational Complexity
Scientific paper
2002-05-04
Computer Science
Computational Complexity
19 pages, 16 figures. Version 4 adds token formulation and minor corrections. To appear in Theoretical Computer Science
Scientific paper
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. 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 (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 puzzles are PSPACE-complete, of which we also give a simpler proof. Finally, we strengthen the existing result that the pushing-blocks puzzle Sokoban is PSPACE-complete, by showing that it is PSPACE-complete even if no barriers are allowed.
Demaine Erik D.
Hearn Robert A.
No associations
LandOfFree
PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-351356