C'est parce qu'ils se foutent de résoudre des instances réelles du problème ?
Oui, et il n'y a pas qu'eux : Personne sur cette planète n'en à rien à foutre de résoudre le problème. Ce qui les importes, c'est de savoir que "ça c'est dans P".
Peu leur importe de savoir que en fait leur algo était aussi O(n14·7) et qu'on pouvait faire des algos O(n3) avec des améliorations chiantes à prouver. Par contre, les théorèmes intermédiaires (ou la démarche pour les obtenir) pourront être réutilisés pour faire quelque chose d'utile.
Dans la pratique, un algo en O(n42) n'a pas vraiment d'intérêt
Y a des algos exponentiels qui sont utilisés pour traiter des problèmes NP avec des instances avec des tailles en millions. Par contre ils ont des tas d'heuristiques qui détectent les instances ou les parties d'instances faciles ...
[^] # Re: Les vrais théoriciens s'en foutent
Posté par Batchyx . En réponse à la dépêche Le colonel Moutarde, sur la table (de hachage), avec un livre de maths. Évalué à 1.
Oui, et il n'y a pas qu'eux : Personne sur cette planète n'en à rien à foutre de résoudre le problème. Ce qui les importes, c'est de savoir que "ça c'est dans P".
Peu leur importe de savoir que en fait leur algo était aussi O(n14·7) et qu'on pouvait faire des algos O(n3) avec des améliorations chiantes à prouver. Par contre, les théorèmes intermédiaires (ou la démarche pour les obtenir) pourront être réutilisés pour faire quelque chose d'utile.
Y a des algos exponentiels qui sont utilisés pour traiter des problèmes NP avec des instances avec des tailles en millions. Par contre ils ont des tas d'heuristiques qui détectent les instances ou les parties d'instances faciles ...