The Wikipedia article on the unknotting problem says "a major unresolved challenge is to determine [...] whether the problem lies in the complexity class P". It mentions some work towards this result and a recent claim that it is true. But then finally it says "the unknotting problem has the same computational complexity as testing whether an embedding of an undirected graph in Euclidean space is linkless," referencing this paper. Doesn't that statement imply that the unknotting problem is in P, by the graph minor theorem and the existence of a polynomial time algorithm to test for a specific minor in a given graph? What am I missing here? What is the current status of this problem?


1 Answer 1


There is a difference between the following two problems.

(1) Decide if a given abstract graph $G$ admits a linkless embedding in $\mathbb{R}^3$. [This can be solved in polynomial time, as you observe. The authors of the cited paper call this the "flat and linkless embedding" problem.]

(2) Decide if a given embedding of an abstract graph $G$ into $\mathbb{R}^3$ is linkless. [This is the subject of Conjecture 1.1 if the cited paper. The authors prove this polynomial time, relative to an oracle for the "link" problem.]

Basically, in (2) you are given a fixed embedding that you have to understand. This is a lot more information than just the abstract graph, and appears to make the problem harder.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .