Question: Given a `hard' diagram of a knot, with over a hundred crossings, what is the best algorithm and software tool to simplify it? Will it also simplify virtual knot diagrams, tangle diagrams, and link diagrams?
The reason that I ask this question is that I have been reading:
Lewin, D., Gan O., Bruckstein A.M.,
TRIVIAL OR KNOT: A SOFTWARE TOOL AND ALGORITHMS FOR KNOT SIMPLIFICATION,
CIS Report No 9605, Technion, IIT, Haifa, 1996.
This technical report is notable not only for its mathematical content, but also for its back-story. It was the undergraduate research project of Daniel M. Lewin, who was a few years later to found Akamai Technology which today manages 15-20% of the world's web traffic, to become a billionaire, and to be the first person to be murdered on 9-11. He is the subject of the 2013 biography No Better Time: The Brief, Remarkable Life of Danny Lewin, the Genius Who Transformed the Internet by Molly Knight Raskin, published by Da Capo Press.
The algorithm used by Bruckstein, Lewin, and Gan doesn't use 3-dimensional topology or normal surface theory, but instead relies on an algorithmic technique called simulated annealing. I suspect that this same technique could be used effectively for other problems in algorithmic topology.
To the best of my knowledge, Bruckstein, Lewin, and Gan's algorithm is unknown to the low-dimensional topology community, but it works very well. Despite it having been written a long time ago, I wonder (for reasons beyond mere curiousity) how far it is from being state of the art today.