Hippopotame (./12288) :
./12285> Faut voir, faut voir, si ça donne un truc en 10^100*n^(10^100), c'est certes polynomial, mais bon.... En tout cas ça motiverait les gens pour l'améliorer...

Il y a quelques années a été inventé l'algorithme AKS pour prouver en temps polynomial la primalité d'un entier, ce qui était une grande avancée théorique... Mais AKS n'était pas (et n'est toujours pas, je crois) compétitif par rapport aux meilleurs algorithmes non polynomiaux

Vi, y a le problème pour résoudre les programmes linéaires : le problème est polynomial, mais tout le monde utilise une méthode exponentielle qui est nettement plus rapide.