سؤال

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?

mario-hardness

لا يوجد حل صحيح

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى cs.stackexchange
scroll top