Friends-and-strangers is PSPACE-complete
arXiv:2402.03685 · doi:10.1016/j.ipl.2025.106573
Abstract
In this paper, we show that the friends-and-strangers problem is PSPACE-complete by reduction from the Ncl (non-deterministic constraint logic) problem.