100, rue des maths 38610 Gières / GPS : 45.193055, 5.772076 / Directeur : Louis Funar

Francis Lazarus

Deciding the contractibility of a curve on the boundary of a three manifold
Vendredi, 3 Juin, 2022 - 10:30
Résumé : 

Deciding if a curve in a simplicial complex is contractible is 
known to be undecidable, even for curves in two dimensional complexes or 
4-manifolds. It is decidable for a curve in a three manifold but the 
complexity status is unknown. We show that the problem is in NP when the 
curve lies on the boundary of a three manifold. To motivate this 
restricted problem we remark that the knot triviality problem reduces to 
it in polynomial time.

Joint work with Erin Wolf Chambers , Arnaud de Mesmay and Salman Parsa

Thème de recherche : 
Salle : 
logo uga logo cnrs