Encuentra Super Mario Bros Incluso hasta Computadoras

Si alguna vez has luchado para resolver un nivel de "Super Mario Bros.", una nueva investigación del Instituto de Tecnología de Massachusetts definitivamente le animarme. El mundo de "Super Mario" es, sin duda matemáticamente duro.

De acuerdo con un nuevo estudio, que será presentado en la Conferencia Internacional sobre la Diversión con Algoritmos de la próxima semana, el mundo se puede construir a partir de las materias primas de "Super Mario" puede ser tan duro como los problemas más difíciles PSPACE.

PSPACE es una clase de la complejidad de la informática, la agrupación de los problemas que tienen un cierto grado de dificultad juntos. PSPACE es el conjunto de todos los problemas que tienen una cantidad "polinomio" de espacio de memoria de resolver, que depende del tamaño de la entrada.

Un algoritmo que necesita para solucionar a través de N números para encontrar el más grande, por ejemplo, necesitaría espacio de memoria proporcional a N. Si queríamos tener una lista de la distancia entre las ciudades de N, necesitaríamos N ^ 2 espacio porque por cada el algoritmo de la ciudad tendría que calcular una distancia para todos los demás.

Algunos problemas en PSPACE podrían ser fáciles de resolver, mientras que algunos pueden ser difíciles de resolver, pero la solución podría ser fácil de verificar. Los problemas más difíciles son difíciles de resolver y también es difícil de verificar. Se puede construir un nivel de "Super Mario" que tomaría un algoritmo tanto mucho tiempo para resolver e igualmente un largo tiempo para navegar incluso si tenía la solución.

"Estoy muy entusiasmado con este tipo de pruebas de dureza, y los he estado presionando mucho en los últimos dos años," Erik Demaine, co-autor del artículo, dijo en un comunicado . 

Y agregó: "Realmente hace acumular una gran cantidad de experiencia que hace que sea más fácil para conquistar problemas. La práctica más que obtenemos como un colectivo, mejor nos encontramos en la solución de estos tipos de problemas. Y es importante conocer las limitaciones de los algoritmos ".

Las matemáticas no tiende a concentrarse en el ahora, por lo que una solución que podría ser obtenido ahora, incluso en los videojuegos, podría encontrar una aplicación importante en años o quizás siglos venideros.