ON THE COMPUTATIONAL-COMPLEXITY OF THE JONES AND TUTTE POLYNOMIALS

被引:289
作者
JAEGER, F
VERTIGAN, DL
WELSH, DJA
机构
[1] UNIV OXFORD MERTON COLL, OXFORD OX1 4JD, ENGLAND
[2] UNIV OXFORD, INST MATH, OXFORD, ENGLAND
关键词
D O I
10.1017/S0305004100068936
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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.
引用
收藏
页码:35 / 53
页数:19
相关论文
共 48 条