In the very easy-to-read [1], Kuperberg shows that, conditioned on the Generalized Riemann Hypothesis, knottedness is in $ \mathsf{NP}$ . As I understand the proof, given a knot-diagram of a knot $ K_1$ , the certificate is both a prime $ p$ and a set of polynomial equations $ S$ of a noncommutative representation of $ \pi_1$ onto $ SU(2)$ , one for each generator of the knot group $ \pi_1(S^3\setminus K_1)$ , along with a solution to $ S=0$ mod $ p$ .

Kuperberg’s proof relies on GRH only to show that the size (bit-complexity) of $ p$ is polynomial in the number of generators of $ \pi_1$ . His proof is a combination of the algebraic topology results of [2] along with the number theory of [3]. He states in passing that because [3] puts problems involving solving systems of polynomial equations over $ \mathbb{C}$ in the Arthur-Merlin complexity class, that also puts knottedness in $ \mathsf{AM}$ as well.

Studying up on [1] and [3], I suspect that the $ \mathsf{AM}$ protocol that Kuperberg has in mind entails finding a prime $ p$ such that not only $ S$ modulo $ p$ is $ 0$ , but also, for some random hash $ H$ onto a codomain of an appropriately small size, $ H(p)=0$ . This shows that there are a lot of primes $ p$ such that $ S$ is satisfiable mod $ p$ (Kuperberg’s $ \mathsf{NP}$ certificate only needs one prime $ p$ .) Such a protocol from [3] is similar to [4], which gives a public coin protocol for Graph Non Isomorphism based on hashing a random permutation of one of the two given adjacency matrices.

However, as addressed in a question from a sister site, it’s not immediately clear how to convert the results of [3] into a private coin protocol.

Is there a way for a verifier to present a prover with one of two knot diagrams, such that if only one of the knot diagrams represents the unknot whereas the other knot diagram is not the unknot, the prover can answer correctly 100% of the time, but if both knot diagrams are of the unknot, the prover only has a 50% chance of answering correctly?

It is noted that [1] also mentions another withdrawn attempt at putting knottedness in $ \mathsf{AM}$ with a private-coin protocol.

Borrowing from the standard private-coin Graph Non Isomorphism, the verifier may randomly apply Reidemeister moves to either the unknot or the given knot, and have the prover determine which she chose to randomly apply. However, I don’t think that the prover would have a 50% chance of answering correctly if the given knot is the unknot; I think she could get an advantage based off of the complexity of the knot diagram presented.

(Because I suspect a positive answer might involve details of the combinatorics of Reidemeister moves, I ask the question here, rather than on sister sites.)

References

[1] Greg Kuperberg. Knottedness is in $ \mathsf{NP}$ , modulo GRH, 2011.

[2] Peter Kronheimer and Tomasz Mrowka. Dehn surgery, the fundamental group and SU(2), 2004.

[3] Pascal Koiran. Hilbert’s Nullstellensatz is in the polynomial hierarchy, 1996

[4] Shafi Goldwasser. Michael Sipser. Private Coins versus Public Coins in Interactive Proof Systems, 1986.