In "Classic Nintendo Games are (Computationally) Hard", a generalized framework based on reducibility of 3-SAT for proving NP-hardness of classic Nintendo games is presented, and several embodiments of the framework's gadgets, implemented in specific games, are shown.
While this is fun and interesting, and seemingly an attractive example of proving NP-hardness to someone who's both relatively new to computational complexity theory and who loves video games, I can't help but think that the proof can be simplified, at least in the specific case of Super Mario Brothers.
To summarize:
- A given formula is mapped to a configuration of gadgets that determine an initial level state, and
- Satisfiability corresponds to completability of the level, and depends on not only the configuration of the level (the formula), but also which paths Mario takes through the level (variable assignments).
However, if we assume such a setup, why are there separate paths for assigning variables and checking clauses? Would it not be possible to simplify the framework by mapping each 3-literal clause to a single screen gadget (of 9 possible, each corresponding to a specific combination of 3 positive or negative literals) stacked on top of one another, sandwiched between two start and end states at the top and bottom respectively?
For example, here's an illustration of one such a gadget that corresponds to the clause $\neg x_1 \lor x_2 \lor \neg x_3$:
Mario enters here
v
* ***************
* *
* *
******** ** ** *** <- and exits via one of these holes, corresponding
* * * * to each variable respectively
* * * * <- pits too deep for Mario to jump out of
***** *****
* * <----- this clause is only satisfiable if Mario
************ ******* travels down the hole corresponding to x_2
* *
* ***************
* *
^ exit path connected to the following clause
Stacking such gadgets embodies the conjunctions in CNF, as Mario must satisfy all of the clauses corresponding to each gadget in order for the level to be completable.
With this suggested framework in mind, it's still possible to map existing formulae to Mario levels (in linear time, by pattern matching and replacing each clause individually), and it's possible for Mario's path through the level to correspond to variable assignments, with these assignments ultimately affecting Mario's ability to complete (satisfy) the level. Further, this simplified model would apply more directly to the actual game, as it wouldn't have to be generalized to allow for gadgets to retain their item states when Mario leaves them, since there are no items required to begin with.
So, what am I missing? Could it simply be that a more extensive framework is required to fit all of the games presented, or is it something more fundamental that could broaden my understanding of the underlying concepts?