On the computational complexity of the Jones and Tutte polynomials

Abstract

Abstract We show that determining the Jones polynomial of an alternating link is # P -hard. This is a special case of a wide range of results on the general intractability of the evaluation of the Tutte polynomial T(M; x, y) of a matroid M except for a few listed special points and curves of the (x, y) -plane. In particular the problem of evaluating the Tutte polynomial of a graph at a point in the (x, y) -plane is # P -hard except when (x − 1)(y − 1) = 1 or when (x, y) equals (1, 1), (−1, −1), (0, −1), (−1, 0), (i, −i), (−i, i), (j, j 2 ), (j 2 , j) where j = e 2πi/3