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:
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.