Aaron Williams, professor of computer science at Simon's Rock, collaborated with Erik Demaine from MIT and Giovanni Viglietta from University of Ottawa to analyze the complexity class of Super Mario Brothers. The result? Their study suggests that users may find PSPACE-hard levels in the trendy video game—or at least in raw materials of the Super Mario world.
Researchers will present their new paper at the International Conference on Fun with Algorithms in Italy next week.