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.