Estudio determina que Super Mario Bros es NP-completo

Teorema 3.1. Decidir si es posible llegar a un punto cualquiera de un nivel de Super Mario Bros es un problema NP-completo.

¿Estamos ante un candidato a un premio de investigación IgNobel? Posiblemente. Investigadores de Bruselas y del MIT han publicado un estudio (PDF) en el que afirman que distintos juegos clásicos de Nintendo son problemas NP-completos. Los juegos analizados son Super Mario Bros, Donkey Kong, Legend of Zelda, Metroid y Pokémon.

Para los no informáticos, el concepto de NP-completo puede ser algo abstracto, pero se podría resumir por ser “un problema muy gordo, tanto que un ordenador no podría encontrar una solución óptima en un tiempo razonable”.

En el estudio se analiza la cuestión de si es posible determinar si un punto dado de una “fase” o “nivel” es alcanzable por el jugador. “Simplemente” eso. La construcción matemática que construyen los autores consiste en una serie de variables (e.g. “Super Mario ha crecido”) y una serie de artilugios o condiciones (e.g. “un bloque que debe ser destruido”).

Cada fase se construye por tanto como una interconexión de estos bloques, siendo el objetivo encontrar un camino desde un punto inicial a uno final (el “objetivo de la fase”):

Las demostraciones usan conceptos avanzados de análisis de complejidad computacional, como el problema 3SAT (“3-satisfiability”) al que los autores demuestran que se pueden reducir casi todos los juegos clásicos, por lo que recomiendo que si quieres saber más leas el paper… ¡pero bajo tu responsabilidad!

Vía: 1

Share

Etiquetado con: , ,
Publicado en: Curiosidades, Programación
2 comentarios sobre “Estudio determina que Super Mario Bros es NP-completo
  1. Tecnoprensa dice:

    Es increíble que se hallan puesto a investigar el super mario.

    Blog de Tecnologia

  2. Anonymous dice:

    Mas bien creo q le jefe les pillo in fraganti

    -¿pero a que jugais en horas de trabajo?

    -eehh…estooo….ehhhh, el mario bros, queee ehhh que estamos viendo…si eso, que esamos viendo si es un problema np-completo.

    –Ahh bueno, entonces seguid, lo de las papas fritas y el cocacoca me lo explicais luego.

Deja un comentario

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

*

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Recibir por correo electrónico:

Varios

Naukas   Mapping Ignorance