3 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
Tetris with Few Piece Types
MIT Hardness Group, Erik D. Demaine, Holden Hall +1
We prove NP-hardness and #P-hardness of Tetris clearing (clearing an initial board using a given sequence of pieces) with the Super Rotation System (SRS), even when the pieces are…
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…