Super Mario Bros probado NP-Hard

En enero, vimos el trabajo de Giovanni Viglietta en la Universidad de Pisa en Italia, quien había demostrado la complejidad computacional de muchos juegos de computadora de los años 80 y 90, como Pac-Man y Tron.

Viglietta señaló que este tipo de análisis es innecesario para los juegos modernos porque la mayoría incorpora lenguajes de secuencias de comandos equivalentes a Turing que permiten fácilmente el diseño de acertijos indecidibles como parte del juego.

Sin embargo, eso todavía deja muchos clásicos que aún no están clasificados.

Hoy, Greg Aloupis de la Universidad Libre de Bruselas en Bélgica y un par de amigos llenan ese vacío, al menos en parte.

Estos chicos demuestran que varios juegos clásicos de Nintendo de los 80 son NP-hard. La lista incluye las tres primeras encarnaciones de Super Mario Bros, Donkey Kong y todos los juegos de Legend of Zelda.

Todos estos juegos son esencialmente iguales en el sentido de que comienzan en un punto específico con el objetivo de alcanzar algún objetivo. La pregunta que hacen Aloupis y compañía es la siguiente: dada la posición inicial, ¿es posible alcanzar la meta?

Si es difícil decidir incluso esta pregunta, entonces ciertamente es difícil encontrar un camino óptimo, dicen.

En este contexto, continúan mostrando que todos los juegos son esencialmente versiones de otro problema llamado 3-SAT, que se sabe que es NP-completo. El proceso aquí es mostrar que 3SAT reduce estos problemas en ciertas circunstancias, demostrando así que son NP-hard.

Entonces, si tu juventud se desperdició jugando Super Mario Bros, Donkey Kong o cualquiera de los otros juegos que estos chicos prueban NP-Hard, entonces saber lo difíciles que fueron en realidad podría brindarte un poco de consuelo de que no perdiste tu tiempo por completo. ¡Por otra parte, probablemente no!

Ref: arxiv.org/abs/1203.1895 : Los juegos clásicos de Nintendo son (NP-) difíciles

esconder