Adele Jackson is a second-year student at the Australian National University, in the Bachelor of Philosophy (Science) program. She has yet to find an area of mathematics she’s not interested in. In particular, Adele is fascinated by fields on the border of maths and theoretical computer science, which let her combine her algorithms background with her university studies.
As well as maths, she has studied environmental science and computer science. Outside of academics she enjoys singing in choirs, all kinds of sport, and helping out with the Australian informatics olympiad training program.
The Unknotting Problem and Fixed-Parameter Tractability
The unknotting problem is to algorithmically recognise whether a given presentation of a knot is in fact ambient isotopic to the trivial knot.The unknotting problem is known to lie in both NP and co-NP, so is a good candidate to additionally be solvable in polynomial time (that is, to lie in P) in the number of crossings. One complexity concept halfway between NP and P is fixed-parameter tractability, where a problem is solvable in polynomial time in the input when another parameter of the input is fixed. I attempt to show that unknot recognition is fixed-parameter tractable using a mix of topological, algebraic, geometric and combinatorial techniques.