Quote:
Originally Posted by waffle
tl;dr cliffs of my post: I saw one of these authors give a talk showing Mario is NP-hard, but it's not a scenario that you face in the actual game. What he shows is NP-hard is a new world built with components from Mario. This tetris result is probably similar, but I haven't looked at it. Details on Mario below if you care.
----------
I actually saw Erik Demaine give a talk proving that Super Mario Bros is NP-hard. It sounded strange because people beat that game all the time. Essentially what he did was build a new level using parts from the actual game, and proved that it was NP-hard to complete this level.
The gist of it is that you repeatedly come to spots where where you have two options: (1) small Mario can run through a "tunnel" that big Mario is too big to fit through, and (2) big Mario can break the blocks above you to reach a new tunnel that small Mario can't get to.
You can essentially choose whether to be big or small each time which fixes which tunnel you can go down, but you can't see what's on the other end of the tunnel when you make your decision. You have one shot to guess, and if you guess wrong you cant reach the end of the level (or maybe you can backtrack but backtracking takes a very long time). If you beat the level you have to guess which tunnel is right many times in a row.
I'd imagine Tetris is similar. They probably set up a new board that is very carefully constructed and is unlikely (or maybe even impossible) to set up in the classic version of the game and then give you a couple options on where to put the next piece. If you guess wrong you lose, if you guess right then you have another decision to make, etc. Again I haven't actually looked at this but I'd guess the result is along these lines.