I had initially thought the same thing, and further that the computational complexity of a game as defined in this paper might be a metric of how challenging a game is.<p>The paper shows that Super Mario Bros. is NP-complete, whereas Zelda games are PSPACE-complete. So Zelda is more complex than Mario (unless P=PSPACE). Is there some subjective way in which Zelda is harder than Mario, that would correspond to the difference? I guess Zelda can feel more cerebral, maybe.<p>More crucially the proofs in this paper rely just on the availability of certain items and level configurations that allow them to build circuits to solve 3SAT or whatever. All the other items and possible configurations in a game are irrelevant. For example they show Zelda OoT is PSPACE-complete because it has puzzles where you push around ice blocks---it is possible to construct such as puzzle where solving the puzzle is PSPACE-complete. All the other puzzles in the game, and also the configuration of real ice block puzzles in the game, do not factor into the proof, all that matters is that ice blocks exist somewhere in the game.<p>So these proofs might point to a potential hard core of cerebral difficulty in games but they ignore many other factors which contribute to enjoyable challengingness. I remember the ice block puzzles in Zelda OoT being pretty tricky, but they certainly don&#x27;t stand out as the most memorable part of the game.