On the computational complexity of the Jones and Tutte polynomials

1 July 1990

journal article
research article
Published by Cambridge University Press (CUP) in Mathematical Proceedings of the Cambridge Philosophical Society

Vol. 108 (1) , 35-53
https://doi.org/10.1017/s0305004100068936

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

Keywords

This publication has 34 references indexed in Scilit:

Some simplified NP-complete graph problems
Published by Elsevier ,2002
Tutte Polynomials and Bicycle Dimension of Ternary Matroids
Proceedings of the American Mathematical Society, 1989
Polynomials for Links
Bulletin of the London Mathematical Society, 1988
Tutte Polynomials and Link Polynomials
Proceedings of the American Mathematical Society, 1988
On the Kauffman polynomial of an adequate link
Inventiones Mathematicae, 1988
Tutte polynomials and link polynomials
Proceedings of the American Mathematical Society, 1988
An evaluation of a link polynomial
Mathematical Proceedings of the Cambridge Philosophical Society, 1986
The computational complexity of matroid properties
Mathematical Proceedings of the Cambridge Philosophical Society, 1980
A decomposition for combinatorial geometries
Transactions of the American Mathematical Society, 1972
The Tutte polynomial
Aequationes mathematicae, 1969