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

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor del blog Gaussianos. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

3 Comentarios

  1. 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

    Publica una respuesta
  2. 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” ¬¬

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Si eres de los que encontraron complicados algunos juegos de consola puedes estar tranquilo,…
  2. Carnaval de Matemáticas 3.14: Hablando de Ciencia en su propio idioma | Hablando de Ciencia - [...] Gaussianos: Calcular la letra del DNI, Demostrado que algunos juegos clásicos de Nintendo son NP-Hard [...]

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.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Uso de cookies

Este sitio web utiliza cookies para que tengas la mejor experiencia de usuario. Si continúas navegando estás dando tu consentimiento para la aceptación de las mencionadas cookies y la aceptación de nuestra política de cookies. Más información sobre las cookies <aquí..

ACEPTAR