| Résume | Étant 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é. |
