Friday June 03, 2016

MIT Says Playing 'Super Mario Bros' Can Be Very Hard

Normally I would laugh at anyone saying Super Mario Bros can be extremely hard but, when it is the big brains over at MIT saying the game "requires exponential time to both solve, and to prove algorithmically," I take their word for it.

That’s the conclusion of a new paper from researchers at MIT, the University of Ottawa, and Bard College at Simon’s Rock. They show that the problem of solving a level in "Super Mario Brothers" is as hard as the hardest problems in the "complexity class" PSPACE, meaning that it’s even more complex than the traveling-salesman problem, or the problem of factoring large numbers, or any of the other hard problems belonging to the better-known complexity class NP.