Para clarificar lo que significa ésto, en primer lugar tenemos que definir ‘clase de complejidad’. Los científicos de computación no sólo se ocupan de resolver problemas complicados, pero también analizan con qué rapidez y eficiencia se resuelven los problemas, dadas las limitaciones del mundo real de trabajo con tiempo finito y la potencia de cálculo de la computadora.
Relacionado: Mercedes-Benz tiene su propio nivel en el Super Mario Maker
Todas estas consideraciones se hacen suponiendo que uno está haciendo los cálculos con una máquina de Turing. Esta maquina es un equipo rudimentario con una sola cinta infinita, que fue concebido por la informática, criptografía, y el pionero de Inteligencia Artificial (IA), Alan Turing. Este tipo de computadoras son funcionalmente equivalentes a los equipos digitales como los entendemos actualmente.
Problemas de clase «P» son aquellos en los que la relación entre el número de elementos que intervienen en el problema (N) tiene una relación de polinomio (de ahí la «P») con la cantidad de tiempo que tarda. Eso significa que el tiempo para resolver se puede expresar en una ecuación que implica la realización de operaciones básicas en N o N planteadas a diversas potencias (N al cuadrado, N al cubo, etc.).
Un ejemplo de un problema P sería determinar qué número dentro de un conjunto de números es el más alto. Debido a que sólo tendría que comprobar cada número una vez y registrar cuál es el más alto encontrado, el tiempo para resolver dependerá directamente de cuán grande sea el grupo de números. La alternativa es una relación exponencial entre N y el tiempo para resolver, que implica que un número elevado a la enésima potencia, puede tomar órdenes de magnitud más tiempo.
Abarcando el conjunto de todos los problemas P es «NP» (polinomio no determinista), donde una solución se puede verificar rápidamente por un algoritmo en tiempo polinómico, pero no puede necesariamente ser resuelto en primer lugar la forma más eficiente. Un ejemplo clásico es la determinación de los factores de números primos de un número arbitrariamente grande.
Determinar si ‘P = NP’ o no, (es decir, si cualquier problema que pueda ser fácilmente controlado también puede ser resuelto fácilmente) es una de las cuestiones más importantes que se ciernen sobre las matemáticas y la informática. Tanto es así que el Instituto Clay de Matemáticas lo ha listado como uno de sus siete Problemas del Milenio. Quien le encuentre solución a cualquiera de estos problemas tendrá $ 1 millón de recompensa por cada uno.
Mientras que los matemáticos suelen coincidir en que P es probable que no es equivalente a NP, nadie lo ha demostrado de manera definitiva. El problema se ha ganado atención suficiente para tener varias referencias a la cultura pop, como en el episodio anterior de Los Simpson, o múltiples alusiones en Futurama.
Un conjunto aún más amplio de problemas, sin embargo, se llama PSPACE, que abarca los conjuntos de ambos problemas P y NP. PSPACE se refiere a problemas en los que hay una relación polinómica entre el número de elementos que intervienen en el problema y la cantidad de espacio necesario para calcular una solución (es decir, la cantidad de memoria las necesidades de ordenador).
Volviendo a donde empezamos, los investigadores demostraron en su estudio que los niveles de Super Mario Bros. pueden ser equivalentes a uno de los más problemas más difíciles de resolver de PSPACE.
«El documento no trata de establecer que alguno de los niveles en las versiones comerciales de Super Mario Brothers son tan difíciles», señaló el equipo de investigación, «sólo que es posible construir niveles de dificultad tipo PSPACE, usando la materia prima del mundo de Super Mario”.
Cualquiera que esté familiarizado con los niveles hechos por fans de Super Mario, pueden atestiguar que el límite superior de complejidad en los niveles elaborados a partir de los componentes elementales del video juego son extremadamente altos.
Las reglas discretas y la complejidad emergente de los videojuegos han creado un excelente banco de pruebas para todo tipo de IA y experimentos informáticos que podrían encontrar aplicaciones en el mundo real. «Matemáticamente, los videojuegos no son muy diferentes de los modelos computacionales de los sistemas físicos del mundo real, y las herramientas utilizadas para probar los resultados de complejidad en un solo podría ser adaptado a la otra», agregó el equipo.
«Estoy muy entusiasmado con este tipo de pruebas de complejidad y destreza matemática, y he estado presionando mucho en los últimos dos años para ir mas allá», explicó el autor principal, Erik Demaine. «Mi esperanza es animar a más personas a hacer esto, porque realmente se acumulan una gran cantidad de experiencia que hace que sea más fácil para conquistar problemas. Cuanta mas práctica que obtengamos como un conjunto colectivo, mejor nos encontraremos para solucionar este tipo de problemas. Y es importante conocer las limitaciones de los algoritmos «.
