I am reading the NP-hardness proof of Super Mario Bros. in the paper "Classic Nintendo Games are (Computationally) Hard" by Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta.

I can get the basic idea of the proof framework presented in Section 2.1. I think I also understand the Start gadget, Finish gadget, Variable gadget, Clause gadget, and Crossover gadget individually used in this proof. See the figure below.

However, I failed to plug these gadgets into the proof framework to construct a complete instance/scenario of Super Mario Bros. Specifically,

  1. In the Variable gadget, Mario chooses the path to fall down. Then Mario goes to some Clause gadget where it hits the item block from below to release a Star. I don't understand how the Variable gadgets are connected to the Clause gadgets so that the orientations (fall down vs. "from below") fit together?
  2. In the Clause gadget, the Firebar is on the right side. However, in the proof framework, the Check path goes from right to left. How can Mario pick the Star as desired in this case?
  3. Where should the Crossover gadgets be plugged in the proof framework? Are the circles between the paths from the Variables to Clauses crossover?


  • $\begingroup$ As mentioned by @lbp-1337 in a (non-)answer, Erik is explaining this NP-hardness proof in the class video; starting at 47:10. $\endgroup$ – hengxin Apr 25 '17 at 13:42

Graph Connection and Gadget Orientation

Short answer to your first question is to use graph algorithms to compute gadget assembly. Erik mentions this briefly. Keep in mind the gadgets don't necessarily have to be oriented as shown above. You could rearrange the gadgets however you wish as long as you retain the edge connections and entrance/exits of the graph.

The idea of "falling down" from a variable is so that there is no way to get back up to it. After you fall down there could be a tunneling system or corridor that allows Mario to get to the bottom side of a clause and hit the question box from below.

Right-to-Left Check Path

You could use the mirror (about the y-axis) of the clause gadget to achieve the capability of going right to left. This would be true for any of these gadgets as long as you kept the entrances and exits hooked up properly using tunnels. You do not gain or lose anything from going right to left versus left to right in SMB. They would be equal movements and since the whole level is on the screen at one time, we are not restricted from going right to left.

The Crossover Gadget

The crossover gadget is placed where edges intersect (edges between literal and clause). This is because SMB is a 2-dimensional game and thus the graph using all these gadgets must be planar. The crossover gadget will then act as a vertex where the two intersecting edges can safely connect and not interfere with each other. They will not interfere because if you enter top left, you can only leave top right and if you enter bottom left you can only leave top center. More on the planarity and edge interference here.

Importantly, the crossover gadget is directional. You can only go left to right through the gadget once. This means the edges must also be directional. Whenever you see an edge from literal to clause there are really two directional edges; (literal -> clause) and (clause -> literal). Which results in there being four crossover gadgets whenever the two directional edges cross with two other directional edges. Erik explains more in the video at 1h1m20s (It won't allow me to link to it because this is my first post).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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