ON THE COMPUTATIONAL-COMPLEXITY OF THE JONES AND TUTTE POLYNOMIALS

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 intractibility 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. © 1990, Cambridge Philosophical Society. All rights reserved.