Trouver le jeu lemmings est d'une complexité NP-complet u_u
Ce matin alors que je m'ennuyais un peu et que je voulais me détendre un peu avant de commencer vraiment la journée, je me suis mis en quête des Lemmings. Pas le film dont je ne connais rien mais du vieux jeu Nintendo (repris je ne sais combien de fois) dont le but était de permettre à une tribut de lilliputien con comme leurs pieds de s'échapper d'un univers hostile.
Ce matin donc, en cherchant après ce jeu je suis tomber par hasard dans wikipedia sur :
"Dans le domaine de la recherche en complexité algorithmique, qui vise à estimer l'efficacité des algorithmes pour résoudre un problème donné, le jeu Lemmings a été classé NP-complet."
NP-complet O.o ?! Kezako ?
Et là, en cliquant, je suis tombé sur la théorie presque complète de la complexité algorithmique... Bobo neurone =_=;;
Mais maintenant je me dis qu'il y a quelques avantage à partir dans la recherche :
"Celui qui arrivera à décider si P et NP sont différents ou égaux recevra le prix Clay (plus de 1 000 000 $)."
$www$
Ce matin donc, en cherchant après ce jeu je suis tomber par hasard dans wikipedia sur :
"Dans le domaine de la recherche en complexité algorithmique, qui vise à estimer l'efficacité des algorithmes pour résoudre un problème donné, le jeu Lemmings a été classé NP-complet."
NP-complet O.o ?! Kezako ?
Et là, en cliquant, je suis tombé sur la théorie presque complète de la complexité algorithmique... Bobo neurone =_=;;
Mais maintenant je me dis qu'il y a quelques avantage à partir dans la recherche :
"Celui qui arrivera à décider si P et NP sont différents ou égaux recevra le prix Clay (plus de 1 000 000 $)."
$www$