What's known about computational complexity of different types of knot invariant polynomials?
For example, Evaluating Jones Polynomial is known to be #P hard. Is there any reference that surveys such complexity results on other knot polynomials?
What's known about computational complexity of different types of knot invariant polynomials? For example, Evaluating Jones Polynomial is known to be #P hard. Is there any reference that surveys such complexity results on other knot polynomials? 


The old (1990) paper, "On the computational complexity of the Jones and Tutte polynomials" (Cambridge link), shows that determining the Jones polynomial of alternating links is #Phard, as the OP notes.
Then, much later, the 2012 book Quantum Triangulations (eds.: Carfora, Marzuoli), says this (p.233):
In the same book, there follows a section entitled "Efficient Quantum Processing of Colored Jones Polynomials," with several references. 


Complexity: Knots, Colourings and Counting By D. J. A. Welsh Has pretty extensive information. 

