Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation