100, rue des maths 38610 Gières / GPS : 45.193055, 5.772076 / Directeur : Thierry Gallay

Arnaud de Mesmay

Complexité algorithmique et théorie des nœuds
Vendredi, 25 Janvier, 2019 - 10:30
Résumé : 
De nombreux problèmes de théorie des noeuds sont extrêmement durs à résoudre informatiquement (par exemple tester si deux noeuds sont équivalents), et pour certains on ne connait même pas d'algorithme (par exemple calculer le nombre de dénouage d'un noeud). Pourtant, très peu de résultats de complexité prouvant que ces problèmes sont effectivement difficiles algorithmiquement ont été établis. Après un survol des principaux résultats algorithmiques en théorie des noeuds, nous expliquerons dans cet exposé comment une construction à base d'anneaux borroméens permet d'établir la (NP-)difficulté de plusieurs problèmes, parmi lesquels la détection d'un sous-entrelacs trivial, le calcul du nombre de désenlacement, de nombreux invariants 4-dimensionnels et du nombre minimal de mouvements de Reidemeister à effectuer pour simplifier un diagramme donné.

Basé sur des travaux en commun avec Yo'av Rieck, Eric Sedgwick et Martin Tancer

Institution de l'orateur : 
Gipsa
Thème de recherche : 
Topologie
Salle : 
4
logo uga logo cnrs