# What is the whole picture of the NP-hardness proof of Super Mario Bros?

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?

• As mentioned by @lbp-1337 in a (non-)answer, Erik is explaining this NP-hardness proof in the class video; starting at 47:10. – 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.