Efficient Computation of the Kauffman Bracket

Original · EN

This paper bounds the computational cost of computing the Kauffman bracket of a link in terms of the crossing number of that link. Specifically, it is shown that the image of a tangle with g boundary points and n crossings in the Kauffman bracket skein module is a linear combination of O(2ᵍ) basis elements, with each coefficient a polynomial with at most n nonzero terms, each with integer coefficients, and that the link can be built one crossing at a time as a sequence of tangles with maximum number of boundary points bounded by C√n for some C. From this it follows that the computation of the Kauffman bracket of the link takes time and memory a polynomial in n times 2C√n.