Descriptive Complexity of Knot Equivalence I was reading a little about knots (in a popular math book that wasn't very good) and the book put forth several knot invariants like the Alexander and Jones polynomials. But these are not complete invariants. This made me wonder "what are some complete knot invariants?" and the obvious next question "what is the descriptive complexity of knot equivalence as an analytic equivalence relation?"
Knot equivalence is an analytic equivalence relation on a Polish space (http://en.wikipedia.org/wiki/Knot_theory#Knot_equivalence) and there do exist complete knot invariants (Complete knot invariant?). But I didn't know if this equivalence relation had been looked at from the descriptive set theory point of view.
 A: For this answer, we will restrict to the class of tame knots, i.e. knots that can be smoothly embedded in $S^3$.
Knot polynomials are often not complete invariants of knots and links. For example, there are several knots known to have trivial Alexander polynomial. While it is open if the unknot is detected by the Jones' polynomial, there are also knots known to have the same Jones' polynomial, for example the Kanenobu knots, named after the knots that appear in Theorem 4 the following paper:

Taizo Kanenobu, Examples on polynomial invariants of knots and links
  Mathematische Annalen. 1986, Volume 275, Issue 4, pp 555-572

Also, there are knots with the same HOMFLY-PT polynomial for example mutant knots, see:

W.B.R Lickorish, Linear skein theory and link polynomials, Topology and its
   Applications, 27 (1987), 265-274.

However, knots can be distinguished up to ambient isotopy by their complements, which is a famous (and non-trivial) theorem of Gordon and Luecke:

Cameron Gordon and John Luecke, Knots are determined by their complements. J. Amer. Math. Soc. 2 (1989), no. 2, 371–415.

It is worth mentioning that the analogous statement does not hold for links and link complements.  
In terms of descriptive complexity, many upper bounds on the descriptive complexity of distinguishing knots are now framed in terms of the descriptive complexity of  distinguishing a specific knot complement from another 3-manifold. Marc Lackenby's recent work along these lines shows that the unknot can be recognized in polynomial time:

Marc Lackenby, A polynomial upper bound on Reidemeister, to appear Annals of Math.
  Currently on the arXiv

A: A perfect timing for this question, since I just uploaded a paper on this topic to arXive (see below). Let us specify the definitions. A knot is a homeomorphic image of the circle in $\mathbb{R}^3$. Two knots are equivalent, if there exists a homeomorphism of the ambient space onto itself taking one knot to the other. Sometimes it's required to be orientation preserving, but for the present context we can w.l.o.g. forget about it. Denote this equivalence relation by $E_K$. A knot is tame if it is equivalent to a smooth or piecewise linear knot. Otherwise it is wild. Note that $E_K$ is therefore induced by an action of a Polish group: The group of homeomorphisms of $\mathbb{R}^3$ onto itself is a Polish group (see e.g. Kechris Descriptive set theory) and it acts on knots by $k\mapsto h(k)$. This gives an upper bound to the complexity of knot equivalence: it is below the universal equivalence relation induced by a Polish group action. Denote the latter by $E_U$. 
Usually knot theorists study tame knots. But for tame knots the question of descriptive complexity trivializes, because there are only countably many different knots (each knot is determined by a finite graph with crossing information representing one of its knot diagrams). Moreover each of these knot types is Borel (by Theorem (15.14) (Miller) from the book by Kechris the orbits of a continuous action of a Polish group are Borel sets), so there is a Borel classification of tame knots by natural numbers. In case of tame knots, it is more appropriate to look at the computational complexity of the knot equivalence and there are some results on this topic, see e.g. http://arxiv.org/abs/math/9807016v1 
So what about all knots, including wild knots? As mentioned in the question there are complete invariants for tame knots such as (the knot group + some generators), but can there be such complete invariants of all knots? The answer is 'no', if these invariants are required to be countable structures considered up to isomorphism. I proved this here: http://arxiv.org/abs/1504.02714
by partially answering the question "Where does $E_K$ stand in the Borel reducibility hierarchy of analytic equivalence relations?". In this paper it is proved that $E_K$ is strictly above the isomorphism relation on countable structures (denote this by $E_G$ where $G$ stands for graphs as graphs are as complicated as countable structures can get). On the other hand, by the above, $E_K$ is not above $E_U$. Thus, $E_G\lneq E_K\leqslant E_U$, where the order is the Borel-reducibility of equivalence relations. It remains open whether $E_K$ is exactly as complicated as $E_U$ or is it strictly between $E_G$ and $E_U$, i.e. whether $E_U\leqslant E_K$ or not?
