Kuperberg's [Knottedness is in $\mathsf{NP}$, modulo GRH](https://arxiv.org/pdf/1112.0845.pdf) provides a certificate that a knot $K$ given by a knot diagram on $c$ crossings is not trivial. The certificate is a prime $p$, along with a solution in $\mathbb{Z}/p$ to a system of $m$ polynomial equations on $n$ variables describing a representation of the knot group $\pi\_1(S^3\setminus K)$ onto $\mathrm{SU(2)}$. Assuming the Generalized Riemann Hypothesis, the bit complexity $\log\_2 p$ is polynomial in $m,n$, which are polynomial in $c$.


Letting each polynomial $f\_i$ be of degree at most $d$, the problem is to find a solution to:


$$f\_1[x\_1,x\_2,\cdots,x\_n]=f\_2[x\_1,x\_2,\cdots,x\_n]=\cdots=f\_m[x\_1,x\_2,\cdots,x\_n]=0$$


in $\mathbb{Z}/p$. Thought of as a $\mathsf{SAT}\_p$ problem, for each $f\_i$ we are asked to find a solution $f\_i=0\mod p$.


However, we don't *a-priori* know $p$- the prime modulo which a solution is guaranteed to exist. We only know that there is at least one solution for at least one $p$ not bigger than some number that I'll call $B$.



> 
> Accordingly, is there any advantage to repeatedly *guessing* $n$ integers $\le B$, plugging these numbers in to the $m$ polynomials, and calculating the $\gcd$ of the resulting $f\_i$, stopping when the $\gcd\ne1$?
> 
> 
> 


If the $\gcd\ne 1$, we can think of it as a product of primes $p\_1\times p\_2\times\cdots$. Thus, there will be a solution in $\mathbb{Z}/p\_1,\mathbb{Z}/p\_2,\cdots$, and we know Kuperberg's certificate exists (although we might not know what the prime is unless we can factor the $\gcd$.)


There's an old adage that we can shoot an arrow at a wall and aim for a bulls-eye, but perhaps it's more efficient to shoot the arrow at the wall and draw a bulls-eye around wherever the arrow lands. But perhaps there are too few primes with solutions, or too few solutions modulo any given prime, to make such guessing worthwhile.



How hard is it to guess Kuperberg's certificate of knottedness?
This question is probably very open if we want to be rigorous. With the roughest heuristics, the chance $p$ divides a polynomial value $f\_i$ is $1/p$, and so the chance of recovering $p$ is $1/p^n$ where $n$ is the number of polynomials. Now if we sum over all primes and $n>2$ the expected number of solutions is less than $1$. While we know there is a solution, we won't find it by random search by this heuristic argument.


