Exhibit 1, in no particular order, is the following result, by Hara, Tani and Yamamoto:
Unknotting is in AM ∩ co-AM
Unknotting is one of the more fundamental problems in knot theory. If we think of a (tame) knot as a (really tangled) loop in three dimensions, then much of simple knot theory focuses on the question: Given two knots, are they equivalent ? (where equivalence is expressed in terms of homeomorphisms).
The trivial knot (or the "unknot") is the simple circle in 3D, and thus the unknotting problem is:
UNKNOTTING: Given a knot, is it equivalent to the unknot ?
It was first shown in 1961 by Haken that Unknotting was decidable. After a brief gap of 36 years, Haas, Lagarias and Pippenger showed that Unknotting was in fact in NP (!), and conjectured that it was in NP ∩ co-NP. Other results along the way showed that Genus (is the genus of a knot less than g) was in PSPACE, and ManifoldGenus (a generalization to a given arbitrary manifold), was NP-Complete.
The new result speaks for itself. Formally, the authors show that Knotting (the complement of Unknotting) is in AM, by presenting a two-round interactive protocol for it. They also mention a corollary that if Unknotting is NP-Complete, then PH collapses to the second level. If I had paid better attention in my complexity class I would have figured out how this follows, but alas... I'd be grateful for any enlightenment. (Update: here it is)
The tragedy for me is that although it is clear that this result is interesting, the proof itself is rather impenetrable, requiring a knowledge of combinatorial topology above and beyond what I can muster up. This is why translators are needed ! (Update: here it is)
Knot theory is a good example of a (relatively arcane) subfield of mathematics that has suddenly become profoundly important in "real life". For more on this, read what well-known theoretical computer scientist John Baez has to say :).
On a more frivolous note, you can do knot art ! Calling our resident mathematical knot knitter...
Translation time!
ReplyDeleteThe paper relies on a construction (due to Haken?) of a triangulated 3-dimensional manifold M(K) from a given knot K, such that M(K) is homeomorphic to the 3-sphere if and only if K is unknotted. Specifically, M(K) consists of two copies of S^3-T(K), glued along their boundaries (which are toruses), where T(K) is a tubular neighborhood of the knot K.
So one algorithm for deciding whether a knot K is trivial is to construct M(K) and check whether M(K) is the 3-sphere. The 3-sphere recognition problem is in NP (http://front.math.ucdavis.edu/math.GT/0407047). Haas et al. used a slightly different technique to prove that UNKOTTING is in NP, but both NP-proofs rely on something called "normal surface theory" introduced by Haken in the early 1960s to boil everything down to integer programming(!).
Hara, Tani, and Yamamoto describe an interactive proof protocol for UNKNOTTING based on this characterization, and similar to an interactive protocol for graph isomorphism. The prover is trying to convince the verifier that her knot is nontrivial. The verifier constructs two triangulated 3-manifolds—the manifold M(K) described above, and a particular triangulation S(K) of the 3-sphere. After randomly permuting the vertex labels, the verifier presents the prover with a one of the two triangulations, chosen uniformly at random, without telling the prover which it is. The prover then (supposedly) tells the verifier whether his given manifold is the 3-sphere.
(1) If the prover says that S(K) is the 3-sphere, the verifier learns nothing.
(2) If the prover says that S(K) is NOT the 3-sphere, the verifier knows he's lying and assumes the knot is trivial.
(3) If the prover says that M(K) is the 3-sphere, the verifier assumes the knot is trivial.
(4) if the prover says that M(K) is NOT the 3-sphere, the verifier assumes the knot is nontrivial.
If the knot is trivial, then no prover can convince this verifier with probablity better than 1/2. If the knot is nontrivial, an honest prover can convince this verifier with probability 1/2. Running this protocol twice inflates the probabilities to 1/4 and 3/4.
Posted by Jeff Erickson
I'm curious why you guys care about this proof. Is it just because you like knots and complexity or is it because some allege that it's tied to string theory (see Not Even Wrong for an opinion that string theory is probably nonsense).
ReplyDeletePosted by Anonymous
It's (ahem) "just" because we like knots and complexity. These are fundamental mathematical questions, much more important than this so-called "reality" that physicists keep arguing about. String theory is about as relevant to our interest as thunderstorms or dancing bears.
ReplyDeletePosted by Jeff Erickson
Well said, Jeff. I actually have a post lined up that talks about this, liberally referencing a stunning lecture given by Timothy Gowers a few years ago on the importance of math (where he mentions knot theory, btw).
ReplyDeleteIn short, mathematicians like math for various reasons, but very few of these reasons have to do with so-called "practical impact". I would not object if some of my work has some practical relevance, but that is not necessarily my goal in pursuing it (and i'm not even a mathematician !)
"Thunderstorms or dancing bears". There's a nice ring to that :)
Posted by Suresh
This comment has been removed by a blog administrator.
ReplyDeleteSuresh, I don't think I've yet knitted a knot; I have baked knotted bagels (trefoil) and knotted challa (figure-8). However, a measure 1 subset of the knot theory done in my household is done by someone else.
ReplyDeletePosted by Rudbeckia Hirta