Some years ago I took a long piece of string, tied it into a loop, and tried to twist it up into a tangle that I would find hard to untangle. No matter what I did, I could never cause the later me any difficulty. Ever since, I have wondered whether there is some reasonably simple algorithm for detecting the unknot. I should be more precise about what I mean by "reasonably simple": I mean that at every stage of the untangling, it would be clear that you were making the knot simpler.
I am provoked to ask this question by reading a closely related one: can you fool SnapPea? . That question led me to a paper by Kaufmann and Lambropoulou, which appears to address exactly my question: http://www.math.uic.edu/~kauffman/IntellUnKnot.pdf , since they define a diagram of the unknot to be hard if you cannot unknot it with Reidemeister moves without making it more complicated. For the precise definition, see page 3, Definition 1.
A good way to understand why their paper does not address my question (by the way, when I say "my" question, I am not claiming priority — it's clear that many people have thought about this basic question, undoubtedly including Kaufmann and Lambropoulou themselves) is to look at their figure 2, an example of an unknot that is hard in their sense. But it just ain't hard if you think of it as a three-dimensional object, since the bit of string round the back can be pulled round until it no longer crosses the rest of the knot. The fact that you are looking at the knot from one particular direction, and the string as it is pulled round happens to go behind a complicated part of the tangle is completely uninteresting from a 3D perspective.
So here's a first attempt at formulating what I'm actually asking: is there a generalization of the notion of Reidemeister moves that allows you to pull a piece of string past a whole chunk of knot, provided only that that chunk is all on one side, so to speak, with the property that with these generalized Reidemeister moves there is an unknotting algorithm that reduces the complexity at every stage? I'm fully expecting the answer to be no, so what I'm really asking for is a more convincing unknot than the ones provided by Kaufmann and Lambropoulou. (There's another one on the Wikipedia knot theory page, which is also easily unknotted if you allow slightly more general moves.)
I wondered about the beautiful Figure 5 in the Kaufmann-Lambropoulou paper, but then saw that one could reduce the complexity as follows. (This will be quite hard to say in words.) In that diagram there are two roughly parallel strands in the middle going from bottom left to top right. If you move the top one of these strands over the bottom one, you can reduce the number of crossings. So if this knot were given to me as a physical object, I would have no trouble in unknotting it.
With a bit of effort, I might be able to define what I mean by a generalized Reidemeister move, but I'm worried that then my response to an example might be, "Oh, but it's clear that with that example we can reduce the number of crossings by a move of the following slightly more general type," so that the example would merely be showing that my definition was defective. So instead I prefer to keep the question a little bit vaguer: is there a known unknot diagram for which it is truly the case that to disentangle it you have to make it much more complicated? A real test of success would be if one could be presented with it as a 3D object and it would be impossible to unknot it without considerable ingenuity. (It would make a great puzzle …)
I should stress that this question is all about combinatorial algorithms: if a knot is hard to simplify but easily recognised as the unknot by Snappea, it counts as hard in my book.
Update. Very many thanks for the extremely high-quality answers and comments below: what an advertisement for MathOverflow. By following the link provided by Agol, I arrived at Haken's "Gordian knot," which seems to be a pretty convincing counterexample to any simple proposition to the effect that a smallish class of generalized moves can undo a knot monotonically with respect to some polynomially bounded parameter. Let me see if I can insert it:
(J.O'Rourke substituted a hopefully roughly equivalent image for Timothy's
now-inaccessible image link.)
I have stared at this unknot diagram for some time, and eventually I think I understood the technique used to produce it. It is clear that Haken started by taking a loop, pulling it until it formed something close to two parallel strands, twisting those strands several times, and then threading the ends in and out of the resulting twists. The thing that is slightly mysterious is that both ends are "locked". It is easy to see how to lock up one end, but less easy to see how to do both. In the end I think I worked out a way of doing that: basically, you lock one end first, then having done so you sort of ignore the structure of that end and do the same thing to the other end with a twisted bunch of string rather than a nice tidy end of string. I don't know how much sense that makes, but anyway I tried it. The result was disappointing at first, as the tangle I created was quite easy to simplify. But towards the end, to my pleasure, it became more difficult, and as a result I have a rather small unknot diagram that looks pretty knotted. There is a simplifying move if one looks hard enough for it, but the move is very "global" in character — that is, it involves moving several strands at once — which suggests that searching for it algorithmically could be quite hard. I'd love to put a picture of it up here: if anyone has any suggestions about how I could do this I would be very grateful.
Best Answer
As you suggest, a lot of people have thought about this question. It's hard to find arrangements of an unknot that are convincingly hard to untie, but there are techniques that do pretty well.
Have you ever had to untangle a marionette, especially one that a toddler has played with? They tend to become entangled in a certain way, by a series of operations where the marionette twists so that two bundles of control strings are twisted in an opposite sense, sometimes compounded with previous entanglements. It can take considerable patience and close attention to get the mess undone. The best solution: don't give marionettes to young or inattentive children!
You can apply this to the unknot, by first winding it up in a coil, then taking opposite sides of the coil and braiding them (creating inverse braids on the two ends), then treating what you have like a marionette to be tangled. Once the arrangement has a bit of complexity, you can regroup it in another pattern (as two globs of stuff connected by $2n$ strands) and do some more marionette type entanglement. In practice, unknots can become pretty hard to undo.
As far as I can tell, the Kaufmann and Lambropoulou paper you cited deals is discussing various cases of this kind of marionette-tangling operation.
I think it's entirely possible that there's a polynomial-time combinatorial algorithm to unknot an unknottable curve, but this has been a very hard question to resolve. The minimum area of a disk that an unknot bounds grows exponentially in terms of the complexity of an unknotted curve. However, such a disk can be described with data that grows as a polynomial in terms of the number of crossings or similar measure, using normal surface theory. It's unknown (to me) but plausible (to me) that unknotting can be done by an isotopy of space that has a polynomially-bounded, perhaps linearly-bounded, "complexity", suitably defined --- that is, things like the marionette untangling moves. This would not imply you can find the isotopy easily---it just says the problem is in NP, which is already known.
One point: the Smale Conjecture, proved by Allen Hatcher, says that the group of diffeomorphisms of $S^3$ is homotopy equivalent to the subgroup $O(4)$. A corollary of this is that the space of smooth unknotted curves retracts to the space of great circles, i.e., there exists a way to isotope smooth unknotted curves to round circles that is continuous as a function of the curve.