Etant donnée une courbe $c$ dans une $3$-variété triangulée $M$, comment déterminer si $c$ est contractile ?

Dans la suite, nous supposons toujours que $c$ est sur le bord de $M$. Le cas où $c$ est sans auto-intersections a été étudié par Hass, Lagarias et Pippenger (1999) en utilisant la notion de surfaces normales, en lien avec le problème du noeud ; ils montrent que le problème est dans NP, ce qui donne un algorithme exponentiel. Je décrirai un algorithme avec la même complexité qui résout le problème dans le cas plus général où $c$ peut avoir des auto-intersections. La méthode repose de façon clé sur la démonstration du Loop Theorem.

Cet exposé, résultat d'un travail en commun avec Salman Parsa, ne nécessite aucune connaissance préalable en algorithmique et complexité.