What Makes Mario NP-Hard? (Polynomial Reductions)

Undefined Behavior
Undefined Behavior
38.7 هزار بار بازدید - 6 سال پیش - We think of Mario as
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: Twitter: UBehavior

Created by: Cory Chang
Produced by: Vivian Liu
Script Editor: Zachary Greenberg
Music: Gravity Sound (@gravitysound)

—

References:
Paper: https://arxiv.org/abs/1203.1895
Reduction: https://en.wikipedia.org/wiki/Reducti...)
3-SAT: https://en.wikipedia.org/wiki/Boolean...
P vs NP Playlist: P vs NP
6 سال پیش در تاریخ 1397/11/08 منتشر شده است.
38,796 بـار بازدید شده
... بیشتر