<p><strong>No</strong>, at least not with the suggested approach.</p>
<p>There are (at least) two crucial issues with this approach:</p>
<ul>
<li>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.</li>
<li>The example gadget actually models a conjuction, not a disjuction. It <em>is</em> 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.</li>
</ul>

CC BY-SA 4.0
2021-11-25T08:16:29.013Z
2021-11-25T08:22:11.617Z
2021-11-25T08:22:11.617Z
ferris
<p>In <a href="https://arxiv.org/abs/1203.1895" rel="nofollow noreferrer">&quot;Classic Nintendo Games are (Computationally) Hard&quot;</a>, 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.</p>
<p>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.</p>
<p>To summarize:</p>
<ul>
<li>A given formula is mapped to a configuration of gadgets that determine an initial level state, and</li>
<li>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).</li>
</ul>
<p>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?</p>
<p>For example, here's an illustration of one such a gadget that corresponds to the clause <span class="math-container">$\neg x_1 \lor x_2 \lor \neg x_3$</span>:</p>
<pre><code> Mario enters here
   v
*     ***************
*                   *
*                   *
********  **  **  *** &lt;- and exits via one of these holes, corresponding
       *   *  *   *      to each variable respectively
       *   *  *   * &lt;- pits too deep for Mario to jump out of
       *****  *****
           *  * &lt;----- this clause is only satisfiable if Mario
************  *******  travels down the hole corresponding to x_2
*                   *
*     ***************
*     *
   ^ exit path connected to the following clause
</code></pre>
<p>Stacking such gadgets embodies the conjunctions in CNF, as Mario must satisfy <em>all</em> of the clauses corresponding to each gadget in order for the level to be completable.</p>
<p>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.</p>
<p>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?</p>

CC BY-SA 4.0
2021-10-01T22:22:33.203Z
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?
Yonatan N
CC BY-SA 4.0
2021-10-02T05:38:45.633Z
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!
ferris
CC BY-SA 4.0
2021-10-02T05:45:37.057Z
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).
ferris
<np-hardness><sat><reductions><boolean-formulas>
Can this NP-hardness proof for Super Mario Brothers (and other games) be simplified?
ferris
# Can this NP-hardness proof for Super Mario Brothers (and other games) be simplified?

(Asked by: username_0 on 2021-10-01)

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?

**Tags:** np-hardness, sat, reductions, boolean-formulas
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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!  
> **username_0**: 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).  

---

## 1 answers

### Answer by username_0 on 2021-11-25. Score: 0 | Accepted answer

**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.


---

