What Makes Mario NP-Hard? (Polynomial Reductions)

We think of Mario as an influential platforming game, but it also has interesting connections to complexity theory. In this video, we explore what makes Mario NP-hard.

Created by: Cory Chang
Produced by: Vivian Liu
Script Editor: Zachary Greenberg

—

References:

[patrickwienhoft]

Does this make Mario NP-complete?
We should be able to check in polynomial time whether a given solution is correct. First, simplify a bit by introducing doors. this makes the whole process more linear. Then we get a simple input sequence of "Door > left/right > ground pound > door > left/right > ... > grab star > run through fire > grab star > ... > flag" which should be checkable in poly time.

This only applies to our simplified Mario version. However, on a lower level you might even argue that checking whether a given inpute sequence in a game, say Mario Maker, beats the level. This should also be polynomial since the time required in linear in the number of frame inputs (i.e. frame amount/60).

So I believe Mario is in NP and, given the NP-hardness, also NP-complete.

[ianprado]

Also, how do you only have 13k subs? Your content is amazing

[xD]

The original paper relaxed the constraints on level design slightly by allowing levels more than one screen (13 tiles) high, and allowing scrolling to the left. An interesting question is the complexity of the original NES SMB1 with its original mechanics, without these generalizations.

[ISoulreaverI]

someone has to make a level like this in mario maker if it doesnt already exist

[SA-cyih]

came here with no understanding of np and got out with a vast knowledge on a game that I've never played, thank u my broski

[eladaharon]

Amazing! I really like your animations, "Undefined Behavior" channel helped me so much understanding complexity :)

[GabrielsEpicLifeofGoals]

There's been Turing Machines, calculators, 51-checkpoint levels, near-impossible levels with 1 nonvigintillion chance of guessing a correct combination, and more in Super Mario Maker 2!

[wavejumper]

That picture of the model was 2SAT tho? Which is P? Uhhhh

[johnlarson]

You make good and interesting videos. I just discovered your channel. I hope you didn't quit making them.

[jondo]

6:05
Classic Mario can't ground-pound

[patrickwienhoft]

Hm, but is the reduction doable in polynomial time? I imagine managing the crossings such that everything works out as intended might get complicated after some time, possibly making us unable to construct the level from a given 3SAT formula in polynomial time.

[barichello_]

08:37 He can also run left and land on the flag

[kinertia]

If Mario is NP-Hard, then what's up with those people claiming that AIs are winning mario? How can you train a computer, which is a Deterministic Turing Machine to complete Mario levels simply by feeding information into it?

[christophertralie]

Love this paper, and the explanation here was really solid and helped me to understand some of the finer points of the crossover gadgets. I'm curious...did you write code to create the level for (x OR y) AND (not x OR not y), or did you make that manually?

[theatheistpaladin]

From a practical standpoint, I would have the problem work backward. Can any part of the pole be reached from the play area? If yes, then continue to work backward to the start line.

[dokotomonaku]

So we reduce an NP-Hard problem to 3SAT in polynomial time. One can try to solve it by asking the verifier, which we were able to reduce it to 3SAT in polynomial time, whether the problem can be solved in each step. Since the answers to these decision problems in each step can be found in ExpTime can we say that NP-Hard⊊ExpTime?

[denischen]

Super Mario Bros. is actually undecidable because you can simulate a Turing machine powered by shells. There is no way to decide whether an arbitrary Super Mario Bros. contraption halts.

[cochaviz]

yoo, now in my last class of computability theory, and this is unironically helpful! :)

[vadrif-draco]

3:49 *animation plays*
brain: *MUSIC ON*

[rolfhuisman]

Given you only used two variables per clause, doesn't this make it 2-sat which is in p ? Shouldn't you have used a three like structure for this ?