>> je sais résoudre des problèmes NP-complets en temps linéaire
> mmm mmm mmm
> En fait si tu sais resoudre en temps lineaire (donc polynomial) ne serait-ce qu'un seul des
> milliers de problemes NP complets qui existent, tu devrais communiquer tes resultats et/ou
> ta methode,
Tu aurais pu citer toute la phrase :
> sur de grosses classes de graphe, je sais résoudre des problèmes NP-complets en temps linéaire.
Ben oui, un problème NP complet est un problème pour lequel on ne connais pas d'algo polynomial dans le pire cas, mais on peu toujours trouver de meilleurs algos dans la plupart des cas si on limite à un sous-ensemble des entrées possibles.
[^] # Re: Comparaison de neuf langages sur un micro-benchmark
Posté par Matthieu Moy (site web personnel) . En réponse à la dépêche Comparaison de neuf langages sur un micro-benchmark. Évalué à 2.
> mmm mmm mmm
> En fait si tu sais resoudre en temps lineaire (donc polynomial) ne serait-ce qu'un seul des
> milliers de problemes NP complets qui existent, tu devrais communiquer tes resultats et/ou
> ta methode,
Tu aurais pu citer toute la phrase :
> sur de grosses classes de graphe, je sais résoudre des problèmes NP-complets en temps linéaire.
Ben oui, un problème NP complet est un problème pour lequel on ne connais pas d'algo polynomial dans le pire cas, mais on peu toujours trouver de meilleurs algos dans la plupart des cas si on limite à un sous-ensemble des entrées possibles.