Si eres de los que encontraron complicados algunos juegos de consola puedes estar tranquilo, realmente lo son. Y digo realmente porque se ha demostrado matemáticamente que algunos juegos de Nintendo están dentro de la clase de complejidad NP-Hard. Para hacernos una idea de la dificultad que esto supone, tened en cuenta que NP-Hard es algo así como al menos tan difícil como NP, y una de las maneras informales que he visto por ahí para describir los problemas que están en NP es que son los problemas intratables.

El paper en cuestión se titula Classic Nintendo Games are (NP-)Hard (en el arXiv) y sus autores son Greg Aloupis, Erik Demaine y Alan Guo. El abstract de este trabajo es el siguiente:

We prove NP-hardness results for five of Nintendo’2 largest video game franchises: Mario, Donkey kong, Legend of Zelda, Metroid and Pokemon. Our results apply to Super Mario Bros. 1, 3, Lost Levels, and Super Mario World; Donkey kong Country 1-3; all Legend of Zelda games except Zelda II: The Adventure of Link; all Metroid games; and all Pokemon role-playing games. For Mario and Donkey Kong, we show NP-completeness. In addition, we observe that several games in the Zelda series are PSPACE-complete.

Vamos, más o menos que prueban que resultados relacionados con la complejidad computacional de varios juegos estrella de Nintendo: Super Mario Bros, Super Mario World, Donkey Kong, Legend of Zelda y Metroid.

(Algunas de las imágenes que aparecen en el artículo)

Por ejemplo, para Super Mario Bros demuestran el siguiente teorema:

Theorem 3.1. It is NP-complete to decide whether the goal is reachable from the start of a stage in generalized Super Mario Bros.

Esto es, que decidir si el final de una pantalla de Super Mario Bros es alcanzable desde el principio de la misma es NP-Completo. Casi nada. Y casi nada también el nivel de frikismo de estos tres cracks que firman el artículo (aunque por aquí en Gaussianos tampoco nos quedamos cortos en lo que a friki se refiere).

Ya entendéis por qué os costaba tanto en algunas ocasiones pasaros alguna de las pantallas, ¿no?


Fuentes y enlaces relacionados:


Este post es mi segunda aportación a la Edición 3.14 del Carnaval de Matemáticas, que organiza Hablando de Ciencia.

Print Friendly, PDF & Email
0 0 votes
Article Rating

¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉


Comparte: