2 papers
cs.CC2024
You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games
MIT Hardness Group, Hayashi Ani, Lilly Hall +5
We prove RE-completeness (and thus undecidability) of several 2D games in the Super Mario Bros. platform video game series: the New Super Mario Bros. series (original, Wii, U, and…
cs.CC2024
PSPACE-Hard 2D Super Mario Games: Thirteen Doors
MIT Hardness Group, Hayashi Ani, Erik D. Demaine +4
We prove PSPACE-hardness for fifteen games in the Super Mario Bros. 2D platforming video game series. Previously, only the original Super Mario Bros. was known to be PSPACE-hard (F…