×
Jaeger, François; Vertigan, D. L.; Welsh, D. J. A.

On the computational complexity of the Jones and Tutte polynomials. (English) Zbl 0747.57006

Math. Proc. Camb. Philos. Soc. 108, No. 1, 35-53 (1990).
From the introduction: “The original problem motivating this paper is to decide whether or not computing the Jones polynomial of a link is, in general, a feasible computation. To put this question into perspective, it is well known that computation of the Alexander-Conway polynomial of a link is ‘easy’ (that is, can be done in time polynomial in the size of the input) being just the expansion of a one-variable determinant, but that the computations of the Homfly and Kauffman polynomials of a link are \(NP\)-hard. The Jones polynomial could be regarded as lying somewhere between the Alexander-Conway polynomial and these two other link polynomials in terms of computational difficulty. However, as we shall see, it turns out to be computationally intractable in a very strong sense, even for the special case of alternating links.” “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 of a matroid”.
Reviewer: B.Zimmermann (Trieste)

Cited in 11 Reviews
Cited in 185 Documents

MSC:

57M25 Knots and links in the \(3\)-sphere (MSC2010)
57M15 Relations of low-dimensional topology with graph theory
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science

Keywords:

computing the Jones polynomial of a link; Alexander-Conway polynomial; \(\#P\)-hard; Tutte polynomial of a matroid
Cite Review PDF
Full Text: DOI

References:

[1] Tutte, Proc. Cambridge Philos. Soc. 43 pp 26– (1947)
[2] DOI: 10.1016/0304-3975(76)90059-1 · Zbl 0338.05120 · doi:10.1016/0304-3975(76)90059-1
[3] DOI: 10.1007/BF01394334 · Zbl 0645.57007 · doi:10.1007/BF01394334
[4] DOI: 10.1016/0040-9383(87)90003-6 · Zbl 0622.57003 · doi:10.1016/0040-9383(87)90003-6
[5] DOI: 10.1063/1.1704825 · doi:10.1063/1.1704825
[6] DOI: 10.1007/BF01817442 · Zbl 0197.50202 · doi:10.1007/BF01817442
[7] Stanley, Enumerative Combinatorics 1 (1986) · Zbl 0608.05001 · doi:10.1007/978-1-4615-9763-6
[8] Brylawski, Matroid Theory 3
[9] DOI: 10.1016/0095-8956(81)90058-7 · Zbl 0474.05028 · doi:10.1016/0095-8956(81)90058-7
[10] Brylawski, Centro Internazionale Matematico Estivo 3 pp 125– (1980)
[11] Brylawski, Proceedings of International Colloquium in Combinatorial Theory 17 pp 83– (1976)
[12] DOI: 10.1016/0095-8956(80)90075-1 · Zbl 0443.05027 · doi:10.1016/0095-8956(80)90075-1
[13] DOI: 10.2307/1996381 · Zbl 0224.05007 · doi:10.2307/1996381
[14] DOI: 10.1016/S0167-5060(08)70508-9 · Zbl 0392.05059 · doi:10.1016/S0167-5060(08)70508-9
[15] Bondy, Graph Theory with Applications (1976) · Zbl 1226.05083 · doi:10.1007/978-1-349-03521-2
[16] Robinson, Math. Proc. Cambridge Philos. Soc. 87 pp 29– (1980)
[17] DOI: 10.1137/0206023 · Zbl 0356.68059 · doi:10.1137/0206023
[18] DOI: 10.1137/0212053 · Zbl 0524.68041 · doi:10.1137/0212053
[19] Baxter, Exactly Solved Models in Statistical Mechanics (1982) · Zbl 0538.60093
[20] DOI: 10.1137/0215050 · Zbl 0606.68066 · doi:10.1137/0215050
[21] Oxley, Graph Theory and Related Topics pp 329– (1979)
[22] DOI: 10.1016/0095-8956(78)90050-3 · Zbl 0321.05108 · doi:10.1016/0095-8956(78)90050-3
[23] MacWilliams, The Theory of Error Correcting Codes (1977)
[24] Lipson, Math. Proc. Cambridge Philos. Soc. 100 pp 361– (1986)
[25] DOI: 10.1137/0607036 · Zbl 0596.68041 · doi:10.1137/0607036
[26] DOI: 10.1112/blms/20.6.558 · Zbl 0685.57001 · doi:10.1112/blms/20.6.558
[27] Vergnas, Ann. Discrete Math. 17 pp 397– (1983)
[28] Vergnas, C. R. Acad. Sci. Paris Ser. A 280 pp 61– (1975)
[29] DOI: 10.1016/0095-8956(80)90082-9 · Zbl 0443.05026 · doi:10.1016/0095-8956(80)90082-9
[30] Kauffman, On Knots (1987)
[31] Kasteleyn, Graph Theory and Theoretical Physics pp 43– (1967) · Zbl 0205.28402
[32] DOI: 10.1090/S0273-0979-1985-15304-2 · Zbl 0564.57006 · doi:10.1090/S0273-0979-1985-15304-2
[33] Zaslavsky, Facing up to arrangements: face count formulas for partitions of spaces by hyperplanes 154 (1975) · Zbl 0296.50010
[34] DOI: 10.1007/BF01010403 · doi:10.1007/BF01010403
[35] DOI: 10.2307/2371182 · Zbl 0012.00404 · doi:10.2307/2371182
[36] Jaeger, Selected Topics in Graph Theory 3 pp 71– (1988)
[37] DOI: 10.1090/S0002-9904-1932-05460-X · Zbl 0005.14602 · doi:10.1090/S0002-9904-1932-05460-X
[38] DOI: 10.2307/2048028 · Zbl 0669.05023 · doi:10.2307/2048028
[39] Welsh, Selected Topics in Oraph Theory 3 pp 43– (1988)
[40] DOI: 10.2307/2047194 · Zbl 0665.57006 · doi:10.2307/2047194
[41] Welsh, Matroid Theory (1976)
[42] DOI: 10.1016/0095-8956(88)90083-4 · Zbl 0595.05033 · doi:10.1016/0095-8956(88)90083-4
[43] Gr?tschel, Geometric Algorithms and Combinatorial Optimization (1988) · doi:10.1007/978-3-642-97881-4
[44] DOI: 10.1137/0208032 · Zbl 0419.68082 · doi:10.1137/0208032
[45] Greene, Stud. Appl. Math. 99 pp 117– (1976)
[46] DOI: 10.1016/0304-3975(79)90044-6 · Zbl 0415.68008 · doi:10.1016/0304-3975(79)90044-6
[47] Garey, Computers and Intractability ? A Guide to the Theory of NP-completeness (1979) · Zbl 0411.68039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.