What Super Mario Bros. Can Teach Us About Computational Complexity

As it turns out, the answer is yes. The researchers demonstrated that solving a generalized level of the classic Nintendo game is a type of computational problem classified as PSPACE-complete.

P, NP, and PSPACE

Quick refresher on computational complexity theory: computer scientists and engineers classify computable problems based on the resources it takes to solve them. Here are three such classes:

• P: A type of problem that can be solved in polynomial time. This means that the time t it takes to compute a solution, as a function of the input size n, is a polynomial (e.g. t=n²).
• NP: A type of problem that can be verified in polynomial time. Verified means it can check whether or not you’ve given it a correct solution to the NP problem; however, it’s an open question as to whether or not the problem is solvable in polynomial time (hence the famous debate: does P=NP?). A well-known example of an NP problem is the travelling salesman problem.
• PSPACE: Instead of considering time as a resource, some complexity classes consider space, i.e., how much memory is required in solving a problem. PSPACE denotes the set of problems that can be solved with a polynomial amount of space. It’s known that both P and NP are subsets of PSPACE, but does P=PSPACE? is still on the list of open questions in computer science. Get on it, compE’s!

The relationship between complexity classes. (Image courtesy of Wikipedia.)

Deconstructing Mario

The engineers built upon previous research wherein they determined that Super Mario Bros is an NP-hard problem, meaning Super Mario Bros is at least as hard as the hardest NP problems. Since all NP problems are PSPACE problems as well, determining that Super Mario Bros is PSPACE-hard is a stronger theoretical result.

Super Mario Bros is a side-scrolling game in which the player controls Mario to avoid enemies, collect coins and reach the end of the level. To study the complexity problem, the engineering team generalized the game to have levels of arbitrary size, and to remember the state of items and enemies even when not shown on the player’s screen.

Of course there are a few more aspects to the game, and the team considers them in depth in their paper. But their general approach involves determining the possible configurations of the game, characterized by the finite arrangement of states such as Mario’s position and velocity, that of his enemies, and the possible interactions between them (considering a constant number of interacting objects).

Why Video Games Are Valuable

You may find yourself asking: “Why?” That’s a fair question, and I’ll let researcher Erik Demaine answer that question:

“My hope is… to encourage more people to do this, because it really does build up a lot of expertise that makes it easier to conquer problems,” he explained. “The more practice we get as a collective, the better we are at solving these types of problems. And it’s important to know the limitations of algorithms.”