Mathematical Proceedings of the Cambridge Philosophical Society

Table of Contents - 1990 - Volume 108, Issue 01  

Research Article

On the computational complexity of the Jones and Tutte polynomials

F. Jaegera1, D. L. Vertigana2 and D. J. A. Welsha2

a1 Laboratoire de Structures Discrètes, Institut IMAG, Grenoble, France

a2 Merton College and the Mathematical Institute, University of Oxford

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

(Received June 26 1989)

(Revised December 06 1989)