Conférence de Benjamin Burton
Unknot recognition is the algorithmic problem of determining whether a knot (i.e., a closed loop) in 3-dimensional space can be untangled. It is a major unsolved question as to whether this problem has a polynomial time solution. Here we present the first conclusive algorithm for unknot recognition which, although exponential time in theory, exhibits a clear polynomial time behaviour in exhaustive practical experiments. The algorithm marries together techniques from computational topology and combinatorial optimisation, and gives a glimpse of the rich potential that integer and linear programming have to offer in the world of 3-dimensional geometry and topology.
Benjamin Burton est un mathématicien, chercheur à l'École de mathématiques et de physique à l'Université du Queensland en Australie.Cliquer ICI pour fermer
Dernière mise à jour : 19/12/2013