Hello,

We noticed you're browsing in private or incognito mode.

To continue reading this article, please exit incognito mode or log in.

Not an Insider? Subscribe now for unlimited access to online articles.

Emerging Technology from the arXiv

A View from Emerging Technology from the arXiv

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

  • March 12, 2012

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

At EmTech MIT, our journalism is brought to life.
Network with like-minded professionals to stay in the know.

Learn more and register
More from Intelligent Machines

Artificial intelligence and robots are transforming how we work and live.

Want more award-winning journalism? Subscribe to Insider Plus.
  • Insider Plus {! insider.prices.plus !}*

    {! insider.display.menuOptionsLabel !}

    Everything included in Insider Basic, plus the digital magazine, extensive archive, ad-free web experience, and discounts to partner offerings and MIT Technology Review events.

    See details+

    Print + Digital Magazine (6 bi-monthly issues)

    Unlimited online access including all articles, multimedia, and more

    The Download newsletter with top tech stories delivered daily to your inbox

    Technology Review PDF magazine archive, including articles, images, and covers dating back to 1899

    10% Discount to MIT Technology Review events and MIT Press

    Ad-free website experience

/3
You've read of three free articles this month. for unlimited online access. You've read of three free articles this month. for unlimited online access. This is your last free article this month. for unlimited online access. You've read all your free articles this month. for unlimited online access. You've read of three free articles this month. for more, or for unlimited online access. for two more free articles, or for unlimited online access.