Citation: Kuperberg, Greg. "How hard is it to approximate the Jones polynomial?." arXiv preprint arXiv:0908.0512 (2009).
Web: https://arxiv.org/abs/0908.0512
Tags: Mathematical, Computer-scientific, Universal-scheme
This paper takes a good look at how hard it is to approximate the Jones polynomial. The conclusion is that the problem of approximating the Jones polynomial is #P hard, in the sense that given two constants A and B it is #P hard to determine whether the Jones invariant of a knot evaluated at a fixed root of unity is less than A or bigger than B.
The point is that the Freedman-Kitaev-Wang proof only gives a polynomial time algorithm for approximating the jones invariant divided by a quantity which grows exponentially with the "bridge number" of the knot. This means that deciding whether a knot has Jones invariant less than A or bigger than B actually grows exponentially with respect to the bridge number, which in turn grows exponentially with respect to the size of the knot! This means that Freedman-Kitaev-Larsen wang can NOT efficiently approximate the Jones polynomial.
This is of course to be compared with the classical result that evaluating the Jones polynomial (and the Tutte polynomials of certain planar graphs) is #P-hard:
> Vertigan, Dirk. "The computational complexity of Tutte invariants for planar graphs." SIAM Journal on Computing 35.3 (2005): 690-712.
> Jaeger, François, Dirk L. Vertigan, and Dominic JA Welsh. "On the computational complexity of the Jones and Tutte polynomials." Mathematical Proceedings of the Cambridge Philosophical Society. Vol. 108. No. 1. Cambridge University Press, 1990.