La complejidad matemática tras Super Mario Bros

Super Mario Bros. uno de los juegos más conocidos de la historia es mucho más complicado matemáticamente de lo que te crees, vamos a ver por qué.

Para entender por qué el Super Mario Bros. es un videojuego tan complejo matemáticamente tenemos que introducirnos en los conceptos de complejidad computacional y la forma de clasifisicar un problema matemático en función del tiempo mínimo que se tarda en resolver.

Esto, curiosamente, nos va a llevar directamente al camino de uno de los problemas matemáticos más famoso del mundo: P contra NP que trata precisamente sobre la complejidad intrínseca de los problemas matemáticos. Pero no temáis que hoy no es el día en que os matamos de aburrimiento. Abrocháos ¡que vamos!

El complejo problema matemático de Super Mario Bros.

contraejemplo matemtico

Para los matemáticos es muy importante saber cómo de complejo es un problema intrínsecamente, es decir, cuánto cuesta resolver un problema suponiendo que utilizamos el método ideal para resolverlo. Estos problemas matemáticos se suelen clasificar en función de la relación entre el número de elementos involucrados y el tiempo o número de pasos que debemos dar para llegar a la solución.

Los dos grupos más famosos son “P” en los que la relación es en forma de polinomio, y “NP” en los que la relacion es un polinomio no determinista. Todo esto sé que parece un tostón, pero aguantad conmigo que merece la pena, lo prometo. El grupo ¨P¨es parte del grupo ¨NP¨ y si subimos un nivel más encontramos el espacio ¨PSPACE¨que engloba a los dos anteriores y además aquellos problemas que guardan una relación binomial, que es más compleja que la anteriores.

Clasificando los problemas matemáticos

PvsNP

Existen más grupos a parte de estos 3 que hemos mencionado, pero para hablar de Super Mario Bros. estos son más que suficientes. El truco de estos grupos es que nos permiten establecer una clasificación en cuanto a la dificultad del problema, que luego se refleja en el tiempo necesario para resolverlo. Esta relación dificultad-tiempo solo se hace realidad para problemas con un gran número de elementos, pero es con lo que se trabaja en la mayoría de casos.

Como podéis imaginaros, los problemas más sencillos son aquellos que solo permencen al grupo “P”, luego más difíciles de resolver son los del grupo “NP” y por último los del “PSPACE”. Y ahora es cuando todo empieza a tener algo de sentido porque los investigadores del MIT han descubierto que los niveles del Super Mario Bros. pueden dar lugar a problemas que se encuentran dentro de “PSPACE”, es decir, con una complejidad mucho mayor que los problemas normales que necesitamos resolver en el día a día.

Ser bueno al Super Mario Bros, no significa ser un genio matemático

Super-Mario-Bros.

El estudio tiene un pequeño truco que es el hecho de que ninguno de los niveles del videojuego tiene la complejidad propia de los problemas “PSPACE” sino que juntando los componentes de los diferentes niveles de dicho videojuego podríamos obtener un nivel con complejidad “PSPACE”. Lo cual explica porque prácticamente cualquiera puede pasarse el videojuego con un poco de entrenamiento pero los problemas “PSPACE” requieren un genio al alcance de pocos.

Lo que sí que resulta curioso es que se podría construir un nivel “PSPACE” en el Super Mario Bros. que sirviera como banco de pruebas para las Inteligencias Artificiales preparadas para resolver problemas “PSPACE”ya que este nivel guardaría muchísima relación con su equivalente matemático. Es decir, Super Mario Bros. podría ser el mejor entrenamiento para las nuevas IA del futuro capaces de resolver problemas matemáticos muy complejos.

Nosotros por si acaso, mientras esperamos a que llegue dicha IA, seguiremos jugando al Super Mario por si acaso se nos ilumina la bombilla y resolvemos uno de los problemas del milenio; total, mal no lo vamos a pasar con un clásico tan maravilloso.

Estudio | MIT