1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ The initial clause is also satisfied by the assignment $x_1 = x_2 = x_3 = \bot$. How are clauses satisfied by negated variables captured here? $\endgroup$
    – Yonatan N
    Oct 1, 2021 at 22:22
  • $\begingroup$ Aha, indeed I’ve made a mistake there; considering the example gadget it’s clear that corresponds to a conjunction rather than a disjunction. I see now in the paper why there are separate variable assignment and clause gadgets; this allows Mario to consistently assign variable values in different clauses. Similar to a logic circuit there are crossing paths in such a setup, so crossover gadgets are required to allow Mario to visit each relevant clause from the relevant variable gadgets. I still feel it can be somewhat simplified, but at least now I know what I was missing. Thanks! $\endgroup$
    – ferris
    Oct 2, 2021 at 5:38
  • $\begingroup$ One way the above gadget could work perhaps is if the formula were converted to DNF and the gadgets were stacked horizontally instead of vertically, with “entry holes” wide enough for Mario to jump over, such that the player would decide only one of the many clauses to traverse. Consistency would not be required because only one clause needs to be satisfied. However this doesn’t work as an np-hardness proof, as 3-SAT is always CNF in the input by definition, and CNF->DNF is np-hard, which prevents it from being used in such a reduction (which must be polynomial time by definition). $\endgroup$
    – ferris
    Oct 2, 2021 at 5:45

1 Answer 1

Reset to default
0
$\begingroup$

No, at least not with the suggested approach.

There are (at least) two crucial issues with this approach:

  • There's no mechanism for ensuring that an assignment to a variable via one gadget is consistent with assignments in other gadgets. This, in particular, is why the original paper had separate variable assignment and clause gadgets.
  • The example gadget actually models a conjuction, not a disjuction. It is possible to build an equivalent 3-SAT instance in DNF using conjuction gadgets stacked horizontally instead of vertically, with “entry holes” wide enough for Mario to jump over, such that the player would decide only one of the many clauses to traverse. Interestingly, in such a formulation, consistency is not required, because only one clause needs to be satisfied. However, crucially, this doesn't work as an np-hardness proof, as 3-SAT is assumed to take CNF as input by definition, and CNF to DNF conversion is np-hard, which prevents it from being used in such a proof reduction, which must be polynomial time.
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.