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.
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:
- No sólo son difíciles… en morvalets.
- NP-Hard en la Wikipedia en español.
Este post es mi segunda aportación a la Edición 3.14 del Carnaval de Matemáticas, que organiza Hablando de Ciencia.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
y yo que me lo pase con menos de 7 años, el 3 si que era un infierno, el penultimo mundo que me mataban y tenia que volver a empezar
Información Bitacoras.com…
Valora en Bitacoras.com: 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……
jajajajaj 🙂
Matemáticas y frikismo 🙂 me encanta
[…] Gaussianos: Calcular la letra del DNI, Demostrado que algunos juegos clásicos de Nintendo son NP-Hard […]
Vaya! Ahora estoy estudiando una asignatura de Ing. Informatica que se llama Algoritmica y el otro día nos mencionaron los problemas NP-completos como el de la mochila. Quiere decir que solo se pueden resolver por algoritmos de fuerza bruta no? que no se puede desarrollar un metodo eficiente para resolverlos no?
Menuda cabeza llevo con los diagramas de deppendencias, es que mañana tengo un examen de esta asignatura del tema «Programación dinamica» ¬¬