http://arxiv.org/abs/1203.1895
"We prove NP-hardness results for five of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokemon."
J'ai juste survolé le début, ça doit pouvoir être vrai pour un paquet d'autres jeux non?
Oui, leurs méthodes sont assez flexibles, et c'est généralisable à un grand paquet de jeu (et intuitivement, ça se tient). Après je ne suis pas du tout familier avec la littérature, donc les subtilités des preuves m'échappent— Chris en saura sans doute plus à ce sujet ^^
L'un des auteurs a fait un papier que j'ai cité dans ma thèse, où il prouve que trouver la meilleure stratégie à Tetris est un problème NP-complet : http://arxiv.org/abs/cs.CC/0210020. C'est passionnant à lire :)
Je vais donc regarder ce nouvel article de près ^^
Erik Demaine (http://en.wikipedia.org/wiki/Erik_Demaine)?
C'est une grosse brute génialissime. License de maths à 14 ans, doctorat à 20 ans, devenu plus jeune professeur dans l'histoire du MIT par la suite.
Il a fait pas mal de recherche en ce qui concerne les mathématiques de l'origami, il est d'ailleurs featuré dans cet excellent documentaire que je recommande:
http://www.greenfusefilms.com/