Are there any very hard unlinks?

Question

This question is closely related to a question of Gowers: Are there any very hard unknots? .
I'm thinking about how to create interesting knots from small numbers of local moves on unlinks. The "standard embedded n-component unlink" (let's call it the untangled unlink) is defined as a union of n circles in n disjoint 3-balls; and an unlink is a link which is ambient isotopic to an untangled unlink. In order to get some feel for what is possible and to have a non-trivial example to play with, I'm looking for an unlink which is difficult to untangle. Paraphrasing Greg Kuperberg's formulation:

Can you untangle any unlink with relatively little work, say a polynomial number of geometric moves of some kind? I'm interested in untangling the components one from another, as opposed to to untangling individual components.

I mean this very much in the same sense that Tim Gowers meant his question: Is there a geometric algorithm to untangle components of any unlink, which "makes the unlink simpler" (this is intentionally vague) at each stage? Conversely, is there an unlink which, if it were given to me as a physical object (some tangled loops of rope), I would not be able to disentangle one component from the other without considerable ingenuity?
At the moment, I am most interested in the question for 2-component links and for 3-component links. It's a bit embarassing that I have no intuition at all for what the answer to this question might look like- the "link case" seems completely different from the "knot case".
Edit: Just an aside: experimentally, it's known that fluids made of long closed molecules flow much faster than fluids made of open molecules, although I don't think that the mathematics behind this is understood. But intuitively, it's clear what's going on- closed molecules don't get tangled up in one another as easily as open ones do. So if hard unlinks exist (and in rheology we're talking unlinks with thousands or millions of components), experimentally we can argue that they must at least be rare. Maybe.

Answer 1

I conjecture that the answer is yes, that you may undo a split link with polynomially many moves. This would yield another proof that unlinking is in NP, but it would be somewhat more satisfying, since the certificate would say that you could actually show someone how to tease apart the two components in polynomial time, rather than some abstract normal surface coordinate certificate.

I have a vague idea how one might use Dynnikov's argument to prove this. He analyzes a sphere in the complement of an arc presentation for the link, by considering an induced singular foliation from an open book, following a method that Birman and Menasco applied to braids. One ought to be able to bound the complexity of this sphere using normal surface theory. There is a nice triangulation of $S^3$ with $n^2$ tetrahedra which has an arc presentation of the link in the 1-skeleton (think of $S^3$ as the join of the two components of the Hopf link with each component having a cell structure with $n$ 1-cells). I think one ought to be able to relate the number of singularities of the foliation with the complexity of the normal 2-sphere with respect to this triangulation, which is at most exponential in $n^2$ (Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger, The Computational Complexity of Knot and Link Problems, J.A.C.M. 46 (1999) 185–211).

Now Dynnikov shows that one may perform exchange moves to decrease the number of singularities of the foliated sphere. In order to get a polynomial number of moves, one would have to show that the number of singularities could be decreased by a definite factor by each move. I suspect this should be true by analyzing things from the normal surface perspective: in a normal surface with exponentially many cells, there are large swaths of the surface which are parallel. If one could eliminate a singularity in the foliation in one part of the surface, then one ought to be able to eliminate singularities in the parallel sheets, and thus eliminate a definite fraction of the singularities. Hopefully this would be similar to the type of algorithm for counting components of normal curves (see Ian Agol, Joel Hass, William P. Thurston, The Computational Complexity of Knot Genus and Spanning Area).

Incidentally, Dynnikov's argument is a bit easier to understand in the split link case, since there are no "boundary conditions" to consider for a sphere versus a disk. An algorithm to detect the unlink gives an algorithm to detect the unknot: just push off a parallel unlinked copy of the knot, and see if the resulting two-component link is split.

Answer 2

This is not a direct answer to Daniel's question, but it could be potentially useful.

Suppose we replace the unlink in the question by a split link $L$ whose components $K_1, \ldots, K_n$ are prime, non-trivial knots. Then, the $K_i$ are separated by a collection of essential two-spheres $S_j$, but these spheres can of course look extremely complicated in a given diagram of $L$. The analogue of Daniel's question in this context is:

Does there exist a fast geometric algorithm that will identify the essential two-spheres in the prime decomposition of $S^3 \setminus L$?

Now, there is a paper of Marc Lackenby that provides some insight into this question:

http://arxiv.org/abs/0805.4706

Starting from an arbitrary diagram of the connected sum $K_1 \sharp \ldots \sharp K_n$, he cuts it into a distant union (split link) $L = K_1 \cup \ldots \cup K_n$, and proves that the essential two-spheres separating these components have to look (relatively) simple in this handle structure. I am very far from an expert on algorithms, but it seems that knowing the essential two-spheres are not too complicated ought to guide a way to "pull them apart", which is what you're after.