Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.