What Makes Mario NP-Hard? (Polynomial Reductions)

Подписаться 28 тыс.

Просмотров 39 тыс.

50% 1

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.
Twitter: / ubehavior
Created by: Cory Chang
Produced by: Vivian Liu
Script Editor: Zachary Greenberg
Music: Gravity Sound ( / @gravitysound )
-
References:
Paper: arxiv.org/abs/1203.1895
Reduction: en.wikipedia.org/wiki/Reducti...)
3-SAT: en.wikipedia.org/wiki/Boolean...
P vs NP Playlist: • P vs NP

Опубликовано:

27 янв 2019

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 79

@ageofdoge Год назад

You are not showing that Mario is NP-Hard, you are just using graphics from Mario to describe a NP-Hard problem. There is no Mario level that looks like this. That's not how the actual mechanics of the game work. I actually can't even really say that because it doesn't seem like you took all the game elements from the same version of Mario and the mechanics vary by game.

@ISoulreaverI 5 лет назад

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

@denischen8196

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.

@kinertia4238 5 лет назад

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?

@0x5D 4 года назад

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.

@ansdor 5 лет назад

that doesn't mean the normal mario gameplay IS np-hard, it just means you can create an np-hard problem simulator using mario mechanics. the 'proof' is absolutely misleading. you can also create the same problem with a circuit board, does it mean circuit boards are np-hard too?

@juhanakaarlehto7754 2 года назад

I'm not an expert but doesn't this just prove that NP-Hard problems can be expressed in Mario so: NP-Hard ⊆ Mario. But it doesn't prove that NP-Hard is a proper subset of Mario (NP-Hard ⊂ Mario). I'm pretty sure that most normal levels in Mario are not Np-Hard, but that doesn't mean you can't create NP-Hard problems in Mario. So I'd say for the most part, Mario is not NP-Hard

@ianprado1488 5 лет назад

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

@handsome_man69

I have herpes

@RandomBurfness 5 лет назад

I'm pretty sure any real level in any real Mario game has way less complexity than NP-hard. :P

@patrickwienhoft7987 5 лет назад

Does this make Mario NP-complete?

@eladaharon9051 5 лет назад

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

@jondo7680 3 года назад

6:05

@johnlarson505 3 года назад

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

@christophertralie9311 2 года назад

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 4 года назад

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.

@cochaviz 3 года назад

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

@jirani82 5 лет назад

anyone got some good books on this?

@dokotomonaku 4 года назад

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?