What Can Be Learned About Computational Complexity From the Famous Super Mario Brothers?

All engineering students, if you ever feel guilty about taking a short video break to break the monotony of your calculus homework, please don’t. If you are doing that you are actually helping in completing a scientific research. A proof for this was recently given by a engineers team that was trying to find answers to one single question: Is Super Mario Brothers Hard? The answer to this question, from their end, turned out to be yes. They demonstrated the results by sorting out a simple generalized level of Nintendo games that can be classified as a kind of computational problem with the name PSPACE-complete. 

 

 

For those who are still looking for clues, let’s refresh your memory on computational complexity theory – computer engineers and scientists classify the computable problems on the basis of the resources that are needed to solve those. The three main classes included under this category are: 

 

• P: It is a kind of problem that can be solved within polynomial time. It means that the amount of time ‘t’ taken to find or compute a solution, as a function of input size ‘n’, happens to be a polynomial (like t=n2).

 

• NP: It is another kind of problem that can be verified within polynomial time. Verification here refers to a check whether you’ve given a right solution or not for the NP problem. Nevertheless, it is an open question that a problem can be solved in polynomial time or not. A well-known example of NP problem is traveling salesman problem. 

 

• PSPACE: Here, in place of considering time as resource, there are some complex classes that consider space as means to solving a problem. PSPACE represents that set of problems that can be solved using a polynomial amount of space. 

 

So, based on this classification, the engineers found out that Super Mario Bros is actually an NP-hard problem. It means Super Mario Bros is as tough as the toughest NP-hard problem. And since, all NP problems happen to be PSPACE problems, determination of Super Mario Bros as a PSPACE-hard can be a stronger theoretical result. Super Mario Bros is actually a side-scrolling game under which Mario is controlled by players to keep foes at bay, collect maximum coins and reach another end of the level. For studying a complexity problem, the team generalized the game to have several levels of arbitrary size and keep in mind the state of items and enemies forever.  No doubt, the game has several other aspects, the team has covered all of those in their paper.