Un peu la flemme de lire l'article, à vrai dire, mais il y a pas mal de possibilités :
- des problèmes qui ne sont compliqués à résoudre que dans des rares cas
- la distribution de ses essais n'est pas franchement bien faite et ne sont pas du tout représentatifs de l'ensemble des problèmes
- l'algo n'est pas totalement polynomial :D (de mémoire, il faut qu'il soit polynomial en la taille de l'instance codée en binaire, et non codée en unaire — exemple bateau : trouver les diviseurs d'un nombre est polynomial quand tu codes en unaire mais exponentiel quand tu codes en binaire)
[^] # Re: Bon, mais cet article ?
Posté par flan (site web personnel) . En réponse au journal P=NP démontré ?. Évalué à 2.
Ça ne veut rien dire.
Un peu la flemme de lire l'article, à vrai dire, mais il y a pas mal de possibilités :
- des problèmes qui ne sont compliqués à résoudre que dans des rares cas
- la distribution de ses essais n'est pas franchement bien faite et ne sont pas du tout représentatifs de l'ensemble des problèmes
- l'algo n'est pas totalement polynomial :D (de mémoire, il faut qu'il soit polynomial en la taille de l'instance codée en binaire, et non codée en unaire — exemple bateau : trouver les diviseurs d'un nombre est polynomial quand tu codes en unaire mais exponentiel quand tu codes en binaire)