Paper Info
Title
The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications
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 restrictedv ertex 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 restrictedto be all dominoes (1脳2 blocks) andthe 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 [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.
Year
DOI
Venue
2002
10.1007/3-540-45465-9_35
ICALP
Keywords
Field
DocType
prior complexity result,main result,edge direction,simple graph model,particular piece,restricted rush hour,nondeterministic constraint logic model,nondeterministic model,existing result,particular edge,generalized rush hour logic,planar graph,directed graph,model of computation,motion planning
Discrete mathematics,Logic model,Combinatorics,Nondeterministic algorithm,Computer science,Constraint graph,Directed graph,Model of computation,True quantified Boolean formula,Planar graph,Computation,Distributed computing
Conference
Volume
ISSN
ISBN
2380
0302-9743
3-540-43864-5
Citations 
PageRank 
References 
7
1.40
3
Authors
2
Name
Order
Citations
PageRank
Robert A. Hearn116920.52
Erik D. Demaine24624388.59