Well, I&#x27;m a programmer and a game programmer so I wouldn&#x27;t say it&#x27;s my homework and I have other things to do with my time.<p>But I guess I&#x27;m not that interested.<p>Some of my examples were chosen as games that can&#x27;t be decided as a decision problem: namely those that use analog electronics, involve chance, have multiple players, or have been solved. Or games that are excessively simple, as I think NP-hard is a pretty unimpressive bound to put on a problem.<p>I&#x27;d rather see someone prove that an extremely simple game can be solved in polynomial time rather than prove a classic or simple game can&#x27;t be solved in polynomial time.<p>And having played the games, the result didn&#x27;t intuitively make sense to me which is why I had to read part of the article to understand that they had extended the games in odd ways, such as making boundless levels. In addition, they have made certain assumptions on the design. They are also not generalized problems so speaking of a generalized solution is... not very sensible.<p>For example, to say that the original Zelda game or one of the first Pokemon games can&#x27;t be solved in polynomial time is dishonest. The game is fixed. A program that determines if the player can get from the beginning to end is trivial: return true. Otherwise, it wouldn&#x27;t have been published. Writing the proof that that program is correct might take quite a bit more time ;). The question is, does that game logic, with any arbitrary campaign or level design, hold to that same standard, and then the answer is no.<p>The paper itself comes very close to refuting its thesis in the first page, when it dictates that there is a finite state that the game machine can have and a finite space for the game. If the hardware that the game runs on has a state space of M, and the level has a size of N, then to prove that a level could never be solved would take on the order of M*N many decisions, at most.<p>The paper and its thesis are completely reliant on its own definitions, which are not clear in the title or the abstract. Really the heading should read: &quot;Classic Nintendo Games Are NP-Hard in Theory&quot;<p>When I have time I will surely read the papers on the field that you have provided.