Je voudrais aujourd’hui illustrer un peu le fonctionnement de la recherche au quotidien.

Notre équipe travaille entre autres sur l’algorithmique des polyèdres convexes. Si vous ne savez pas ce qu’est un polyèdre convexe, peu importe : il suffit de savoir que ce sont des objets mathématiques sur lesquels nous voulons calculer, et que donc nous devons proposer des méthodes de calcul, autrement dit des algorithmes, efficaces, c’est-à-dire calculant le résultat attendu en n’utilisant qu’une quantité réduite de temps et de mémoire.

Un collègue pense avoir l’idée d’une méthode pour vérifier (je ne rentre pas dans les détails) que deux représentations décrivent en fait le même polyèdre. Nous connaissons des méthodes pour cela, mais elles peuvent être inefficaces.

Après recherche dans une FAQ et la bibliographie, il s’avère que dans la première moitié des années 1990 un éminent chercheur a posé la question de l’existence d’une telle méthode efficace. On peut raisonnablement se dire que s’il existait une méthode efficace et assez simple, il l’aurait trouvée.

Toutefois :

  1. Si on commence par partir perdant en se disant que tout ce à quoi l’on peut songer a dû être fait avant par des gens plus forts, on ne fait plus de recherche.

  2. Ce n’est pas parce qu’en 1994 on ne savait pas quelque chose qu’il en est de même en 2017.

  3. Il se peut que la méthode du collègue soit inefficace dans le pire cas, mais que ce pire cas ne se produit que dans des circonstances particulières.

  4. Il se peut que la partie complexe puisse être gérée par des procédures connues souvent efficaces en pratique.

  5. Rien que comprendre dans quels cas l’idée du collègue pourrait être inefficace nous apprendrait des choses.

Affaire à creuser, donc.

(J’ai par ailleurs envoyé des courriels à l’éminent chercheur et à quelques autres auteurs d’articles anciens sur le sujet pour savoir s’ils ont entendu parler de résultats plus récents...)