Skip to Content

Super Mario Bros Proved NP-Hard

Ever wondered how hard those computer games really were? Now computer scientists have proved the computational complexity of various classic Nintendo games

Back in January we looked at the work of Giovanni Viglietta at the University if Pisa in Italy who had proved the computational complexity of many computer games from the 80s and 90s, such as Pac-Man and Tron.

Viglietta pointed out that this kind of analysis is unnecessary for modern games because most incorporate Turing-equivalent scripting languages that easily allow the design of undecidable puzzles as part of the gameplay.

However, that still leaves many classics that are are as yet unclassifed. 

Today, Greg Aloupis at the Free University of Brussels in Belgium and a couple of buddies fill that hole, at least in part. 

These guys prove that several classic Nintendo games from the 80s are all NP-hard. The list includes the first three incarnations of Super Mario Bros, Donkey Kong and all the Legend of Zelda games. 

All these games are essentially the same in that they start at a specific point with the aim of reaching some goal. The question Aloupis and co ask is this: given the starting position, is it possible reach the goal? 

“If it is hard to decide even this question, then it is certainly hard to find an optimal path,” they say.

In this context, they go on to show that all the games are essentially versions of another problem called 3-SAT, which is known to be NP-complete. The process here is to show that 3SAT reduces to these problems in certain circumstances, thereby proving they are NP-hard.  

So if your youth was misspent playing Super Mario Bros, Donkey Kong or any of the other games these guys prove NP-Hard, then knowing how hard they actually were might provide a little comfort that you didn’t waste your time entirely. Then again, probably not!

Ref: arxiv.org/abs/1203.1895: Classic Nintendo Games are (NP-)Hard

Keep Reading

Most Popular

Russian servicemen take part in a military drills
Russian servicemen take part in a military drills

How a Russian cyberwar in Ukraine could ripple out globally

Soldiers and tanks may care about national borders. Cyber doesn't.

Death and Jeff Bezos
Death and Jeff Bezos

Meet Altos Labs, Silicon Valley’s latest wild bet on living forever

Funders of a deep-pocketed new "rejuvenation" startup are said to include Jeff Bezos and Yuri Milner.

conceptual illustration showing various women's faces being scanned
conceptual illustration showing various women's faces being scanned

A horrifying new AI app swaps women into porn videos with a click

Deepfake researchers have long feared the day this would arrive.

ai learning to multitask concept
ai learning to multitask concept

Meta’s new learning algorithm can teach AI to multi-task

The single technique for teaching neural networks multiple skills is a step towards general-purpose AI.

Stay connected

Illustration by Rose WongIllustration by Rose Wong

Get the latest updates from
MIT Technology Review

Discover special offers, top stories, upcoming events, and more.

Thank you for submitting your email!

Explore more newsletters

It looks like something went wrong.

We’re having trouble saving your preferences. Try refreshing this page and updating them one more time. If you continue to get this message, reach out to us at customer-service@technologyreview.com with a list of newsletters you’d like to receive.