Document Type
Article
Department
Computer Science (HMC)
Publication Date
2003
Abstract
In this paper we show that a generalization of a popular motion planning puzzle called Lunar Lockout is computationally intractable. In particular, we show that the problem is PSPACE-complete. We begin with a review of NP-completeness and polynomial-time reductions, introduce the class PSPACE, and motivate the significance of PSPACE-complete problems. Afterwards, we prove that determining whether a given instance of a generalized Lunar Lockout puzzle is solvable is PSPACE-complete.
Rights Information
© 2003 Society for Industrial and Applied Mathematics
DOI
10.1137/S003614450139517
Recommended Citation
J. R. Hartline and R. Libeskind-Hadas, “The Computational Complexity of Motion Planning,” SIAM Review, Vol. 45, No. 3, October 2003, pp. 543-557. DOI: 10.1137/S003614450139517
