Unknotting (proof translation)

Jeff Erickson kindly provides a translation in the comments to my previous post. I reproduce the full comment here, lightly edited for links and with minor corrections/additions marked in italics:

The 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³-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. 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 Kneser in 1929 and used by Haken in the early 1960s to boil everything down to integer programming(!). (For a brief outline of normal surface theory, read the introduction of Benjamin Burton's Ph.D thesis)

Hara, Tani, and Yamamoto describe an interactive proof protocol for KNOTTING based on this characterization, and similar to an interactive protocol for graph non-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.

END PROOF

As an aside, the original two-round interactive proof for graph nonisomorphism is a beautiful example of the power of interactive proofs. It was first demonstrated by Goldreich, Micali and Wigderson in 1986, and I reproduce the proof here in full (for definitions, refer to the original paper).

1. Given two graphs G₁, G₂ on n vertices. the verifier randomly picks i ε {1,2} and a random permutation π of [1..n].
2. Verifier then sends π(G_i) to prover
3. Prover returns j ε {1,2}, and verifier accepts iff j = i.

Proof:
If G₁ and G₂ are nonisomorphic, the prover can figure out which is which by comparing the graph sent by the verifier to G₁ and G₂, and thus will always return the correct answer.

If G₁ and G₂ are isomorphic, the prover cannot tell the difference, and thus can "fool" the verifier with probability 1/2.
QED.