Scientists Prove that Classic Nintendo Games are Hard
Well, not exactly that kind of hard. Computer scientists from MIT and Universite Libre de Bruxelles prove that classic Nintendo games, such as Metroid, Mario, Zelda, and Pokemon belong to a class of mathematical problems called NP-Hard. This means that deciding whether a player can complete them is at least as hard as the hardest problems in NP.
How were they able to prove this? The scientists treated each game as a type of logical puzzle, called the Boolean satisfiability problem. The puzzle asks whether a set of variables in a given formula can be assigned in such a way to force the expression to evaluate to true, or if they actually contradict each other. In the context of the games, enemies and power-ups were treated as statements in the formula. If the set of enemies and power-ups allowed a game to be completed, that is the equivalent to all of the statements in the problem being true. If the resources given to you made a level impossible, that is the equivalent of a contradiction.
Bottom line, there is no easy way for a game designer to check if a game can be successfully completed if it is NP-hard. However, it does make the game interesting. There’s no easy way to decide if you’re going the right or wrong direction, and that is part of what makes these games so much fun.