En Slashdot se hacen eco de que Giovanni Viglietta, investigador italiano de la Universidad de Pisa, ha publicado un estudio donde analiza la complejidad teórica de 13 videojuegos clásicos. Para calcular la complejidad temporal y/o espacial, se basa en reducir los casos a equivalentes a selección de caminos hamiltonianos (NP-completo), determinar la complejidad espacial a partir de compuertas e interruptores, etc. Entran dentro de la complejidad temporal NP-hard: Boulder Dash, Lemmings, Lode Runner, Pac-Man, Pipe Mania, Puzzle Bobble 3, Starcraft, y Tron (PSPACE-completo). Por otro lado, dentro de complejidad espacial, serían PSPACE-hard: Doom y Prince of Persia.

Leer más y comentar: Análisis de complejidad de videojuegos clásicos »