A fascinating new paper describes the difficulty of Mario, Donkey Kong, Zelda, Metroid, and Pokémon games from the perspective of their computational complexity:
http://arxiv.org/abs/1203.1895.
The primary conclusion of the paper is that the intended set of gameplay mechanics in these games places them in the class NP-hard. Without getting into the details of what this means, it is a technical way of saying that, based on very general principles, there is probably no algorithm that can efficiently find the optimal solution to these games (where "probably" refers to the prevailing opinion of computer scientists on important open questions that impact this result, such as P versus NP).
This has important implications for the future of TASes, where ultimately some algorithm must exist that solves these games optimally. In the introduction, the authors even mention tool-assisted speedruns as the motivation for this study.
There are of course various caveats impacting this result in favor of easier solutions, one being that a proof of P = NP would make the efficient solution of these games far more likely. Another is the fact not all NP-hard problems are unrealistic to solve, it's just that the solution time becomes more and more sensitive to the size of the problem. Thus, while the existence of block puzzles in Zelda forces a certain level of complexity upon the algorithms required to solve the game optimally, some block puzzles are far easier to solve than others in terms of the number of possible moves and configurations. It may be that those actually implemented in the games are simple enough that they can still be solved exactly without taking a million years of computer-time.
A third caveat is that there are still open questions about quantum computers. While the computational power of quantum mechanics as currently formulated is known, it may be that a complete theory of quantum gravity requires a modification to quantum mechanics that increases its computational power. Such a possibility also would make the efficient solution of these games more plausible, although it would also require us to have quantum computers in the first place.
A final caveat is that this result doesn't account for the multitude of broken game mechanics that are known to exist (glitches, sequence breaks, etc.). So the problem of determining perfect play within the intended mechanics is almost certainly harder than one that allows various puzzles to be skipped, although finding the set of all possible glitches is another challenge in itself.
Given the exponential growth of computing power, along with various open theoretical questions, and the fact that games can be broken in many ways not intended, there are reasons to believe that there is a path towards the ultimate optimization. It would be a fascinating exercise to analyze even small sections of the existing level design to see if one can prove that a certain combination of moves (and even button presses) is optimal.
