# Computational complexity of 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 #P-hard, as the OP notes. Then, much later, the 2012 book Quantum Triangulations (eds.: Carfora, Marzuoli), says this (p.233):

See the Wikipedia entry on BPQ for a definition: essentially, solvable in polynomial time on a quantum computer, with bounded error probability. It is conjectured that BPQ $\supset$ P.

In the same book, there follows a section entitled "Efficient Quantum Processing of Colored Jones Polynomials," with several references.

-
Prof. O'Rourke, that is a beautiful modern reference; thanks very much. –  Arnab May 27 '12 at 19:45