Is minimum knot crossing number elementary recursive?

Question

One result in knot theory is that link crossing number is NP-hard. Another result is that the equivalence problem for knots and links is elementary recursive. So, given that the equivalence problem is elementary recursive, wouldn't the crossing number be elementary recursive? Say that I have a knot with 42 crossings and I want to find out its minimal crossing number. Once I have all other knots up to and including 42 crossings then I can solve that problem with an upper bound elementary recursive by checking for equivalence with all other knots. But generating all other knots up to and including 42 crossings must not be worse than elementary recursive for it to work. Is it? I read about recent tabulations and could not find the upper bounds. I assume that if it is super-exponential then it is a bottleneck to generate the objects, but if we know that it is at least as efficient as equivalence then it could be claimed that knot crossing number problem has upper bound elementary recursive, and maybe link crossing number too.

I hypothesize that the answer is no: the number of objects for every crossing number grows too fast, but I'm still trying to figure it out and will try and learn more about it.

Answer 1

The number of graphs on $n$ vertices is $$2^{\frac{n(n-1)}{2}}.$$

The number of embeddings of a degree 4 planar graph with $n$ vertices is at most $6^n$. (If you know the clockwise order of the neighbors of each vertex, this determines the embedding.) So there are at most
$$2^{\frac{n(n-1)}{2}} 6^n $$ different embeddings of degree 4 planar graphs with $n$ vertices.

Suppose you have a diagram of a knot with n crossings. This gives an embedding of a degree 4 planar graph with $n$ vertices. And at each crossing, you have a choice of putting the first strand over or under the second. Thus, there are at most $$ 2^n 2^{\frac{n(n-1)}{2}} 6^n $$ different knot diagrams with at most $n$ crossings.

This is an immense overestimate.