On the computational complexity of the Jones and Tutte polynomials

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, j2), (j2, j) where j = e2πi/3