Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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):
 Quantum Triangulations 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.

share|improve this answer
    
Prof. O'Rourke, that is a beautiful modern reference; thanks very much. –  Arnab May 27 '12 at 19:45
add comment

Complexity: Knots, Colourings and Counting By D. J. A. Welsh

Has pretty extensive information.

share|improve this answer
    
"The aim of these notes is to link algorithmic problems arising in knot theory with statistical physics and classical combinatorics. Apart from the theory of computational complexity needed to deal with enumeration problems, introductions are given to several of the topics, such as combinatorial knot theory, randomized approximation models, percolation, and random cluster models." Note: Written a decade ago, so possibly out of date on some topics. –  Joseph O'Rourke May 26 '12 at 0:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.