Demostrado que algunos juegos clásicos de Nintendo son NP-Hard

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.

Share

5 comentarios

  1. Juan | 20 de marzo de 2012 | 16:52

    Vótalo Thumb up 0

    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

  2. Trackback | 20 mar, 2012

    Bitacoras.com

  3. Ramiro Hum-Sah | 24 de marzo de 2012 | 06:06

    Vótalo Thumb up 0

    jajajajaj :)

    Matemáticas y frikismo :) me encanta

  4. Trackback | 26 mar, 2012

    Carnaval de Matemáticas 3.14: Hablando de Ciencia en su propio idioma | Hablando de Ciencia

  5. jabujavi | 29 de marzo de 2012 | 09:50

    Vótalo Thumb up 0

    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” ¬¬

Escribe un comentario

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia. Utiliza la Vista Previa antes de publicar tu comentario para asegurarte de que las fórmulas están correctamente escritas.