In this talk we explore new approaches to the old and difficult computational problem of unknot recognition. Although the best known algorithms for this problem run in exponential time, there is increasing evidence that a polynomial time solution might be possible. We outline several promising approaches, in which computational geometry, linear programming and greedy algorithms all play starring roles.

We finish with a new algorithm that combines techniques from topology and combinatorial optimisation, which is the first to exhibit “real world” polynomial time behaviour: although it is still exponential time in theory, exhaustive experimentation shows that this algorithm can solve unknot recognition for “practical” inputs by running just a linear number of linear programs.

- All seminars.
- Seminars for 2014

Last updated: 06 Nov 2024