But at the time, the researchers couldn’t determine whether it was any harder. The work follows on a paper from two years ago, with two of the same coauthors, which showed that “Super Mario Brothers” is at least as hard as the hardest problems in NP. The new paper doesn’t attempt to establish that any of the levels in commercial versions of “Super Mario Brothers” are PSPACE-hard, only that it’s possible to construct PSPACE-hard levels from the raw materials of the “Super Mario” world. The completion of a level is marked by Mario’s reaching a flagpole. While battling monsters, he must complete various tasks, which can involve navigating brick structures that may rise from the ground plane of the game but may also hang in the air unsupported. In a standard “Super Mario Brothers” game, Mario runs across terrain that unspools from the right side of the screen. 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. That’s the conclusion of a new paper from researchers at MIT, the University of Ottawa, and Bard College at Simon’s Rock. Completing a game of “Super Mario Brothers” can be hard - very, very hard.
0 kommentar(er)
