A Simple Proof that Ricochet Robots is PSPACE-Complete
<|reference_start|>A Simple Proof that Ricochet Robots is PSPACE-Complete: In this paper, we seek to provide a simpler proof that the relocation problem in Ricochet Robots (Lunar Lockout with fixed geometry) is PSPACE-complete via a reduction from Finite Function Generation (FFG). Although this result was originally proven in 2003, we give a simpler reduction by utilizing the FFG problem, and put the result in context with recent publications showing that relocation is also PSPACE-complete in related models.<|reference_end|>
@article{balanza-martinez2024a,
    title={A Simple Proof that Ricochet Robots is PSPACE-Complete},
    author={Jose Balanza-Martinez, Angel A. Cantu, Robert Schweller, Tim Wylie},
    journal={arXiv preprint arXiv:2402.11440},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.11440},
    primaryClass={cs.CC cs.DS}
}