Levels of Super Mario Brothers Can be PSPACE-Hard

Erik Demaine of MIT and his collaborators have demonstrated that one can use the raw materials of the game Super Mario Brothers to construct levels that are PSPACE-hard.

The new paper follows up on prior work that includes a subset of the authors that demonstrated that Super Mario Brothers is NP-hard.