Apr 22, 2014 Comments Off on Overview
Overview
@?Shonan Village Center,?April 28-May 1, 2014
Knot theory is, at its most basic level, concerned with the topology of closed loops in 3-dimensional space.?This mathematical subject is inherently algorithmic: old and fundamental questions include how to test whether two knots are topologically equivalent (isotopic), or how to enumerate all distinct knots up to a given complexity.
Great progress has been made on these problems mathematically, from Haken’s solution to the?unknottedness problem half a century ago [7], to the Gordon-Luecke theorem which converts the broader knot equivalence problem into an algorithmic problem on triangulated 3-manifolds [6].
Nevertheless, algorithmic problems on knots remain challenging for those who wish to do real computations. For instance, the best-known algorithms for just the “simple” problem of testing?unknottedness are exponential-time, and a full enumeration of prime knots has only been carried out for knots of ? 16 crossings [9]. Such problems have now attracted the attention of researchers in algorithms and complexity, as well as other branches of computer science. Examples of current questions include:
- How do algorithmic questions from knot theory fit into the hierarchy of complexity classes? Testing unknottedness is known to be NP [8], and also co-NP assuming the generalised Riemann hypothesis [10]. However, is it in P? Is it NP-complete? Is it fixed-parameter tractable for some natural parameter?
- What are the best methods and heuristics for solving knot problems in practical software? There are many invariants, geometric methods and heuristic techniques that are extremely effective in practice but do not guarantee a conclusive solution [1, 5, 11]?can we prove that these work for average or generic inputs? For a conclusive solution, methods from operations research have proven remarkably effective in testing unknottedness [3], but can these be generalised?
- How can we efficiently generate and effectively manage databases of knots and their properties? The excellent online sources such as KnotInfo [4] and the Knot Atlas [2] are still relatively small (e.g., the exhaustive KnotInfo database contains only the first 2977 prime knots), and generating new data will require a careful interplay between large-scale combinatorial enumeration and complex topological decision problems. As databases grow in scale we must also address issues of computing complex properties in bulk, and effectively exploring and mining the resulting data.
The purpose of this meeting is to bring together experts in computational and algorithmic knot theory. Speakers will range across the spectrum from pure mathematicians to theoretical computer scientists and practical software developers. In particular, we will draw on expertise from a range of inter-related areas:
- development of mathematical software;
- generation and management of data collections;
- computational complexity of knot problems;
- numerical algorithms for studying the geometries of knots;
- discrete algorithms in computational geometry and integer programming;
- visualisation of knots;
- geometric topology, including the tightly related area of 3-manifold topology.
By combining these areas of expertise, we aim to generate new ideas and spawn new long-term projects that can create a clear theoretical picture of the intrinsic algorithmic difficulty of problems in knot theory, and set a new standard for what software can achieve in this rich and complex problem domain.
References
[1] M. V. Andreeva, I. A. Dynnikov, and K. Polthier, A mathematical webservice for recognizing the unknot, Mathematical Software: Proceedings of the First International Congress of Mathematical Software, World Scientific, 2002, pp. 201?207.
[2] Dror Bar-Natan, Scott Morrison, et al., The Knot Atlas, http://katlas.org/, accessed June 2013.
[3] Benjamin A. Burton and Melih Ozlen, A fast branching algorithm for unknot recognition with experimental polynomial-time behaviour, Preprint, arXiv:1211.1079, November 2012.
[4] Jae Choon Cha and Charles Livingston, KnotInfo: Table of knot invariants, http://www.indiana.edu/~knotinfo, accessed November 2011.
[5] Marc Culler, Nathan M. Dunfield, and Jeffrey R. Weeks, SnapPy, a computer program for studying the geometry and topology of 3-manifolds, http://snappy.computop.org/, 1991?2011.
[6] C. McA. Gordon and J. Luecke, Knots are determined by their complements, J. Amer. Math. Soc. 2 (1989), no. 2, 371?415.
[7] Wolfgang Haken, Theorie der Normalflächen, Acta Math. 105 (1961), 245?375.
[8] Joel Hass, Jeffrey C. Lagarias, and Nicholas Pippenger, The computational complexity of knot and link problems, J. Assoc. Comput. Mach. 46 (1999), no. 2, 185?211.
[9] Jim Hoste, Morwen Thistlethwaite, and Jeff Weeks, The first 1,701,936 knots, Math. Intelligencer 20
(1998), no. 4, 33?48.
[10] Greg Kuperberg, Knottedness is in NP, modulo GRH, Preprint, arXiv:1112.0845, November 2011.
[11] W. B. Raymond Lickorish, An introduction to knot theory, Graduate Texts in Mathematics, no. 175,
Springer, New York, 1997.
