How expensive is knowledge? Knots, Links, 3 and 4-manifold algorithms. [closed]

Question

With geometrization, Rubinstein's 3-sphere recognition algorithm and the Manning algorithm, 3-manifold theory has reached a certain maturity where many questions are "readily" answerable about 3-manifolds, knots and links. I'd like to have a community wiki post where we collectively build up a knowledge of just how much is algorithmically known, and how "expensive" it is to know something, in the sense of run-time upper bounds, and memory-usage upper bounds (if available). At worst I'd like to know "there's no known algorithm".

I hope to shape the discussion in this way: This initial post will list the "things we want to know", and the responses will pick off one of these topics and provide details. Whatever details you know, with references and examples of implementations (if available). Preference for algorithms you imagine are genuinely implementable -- ones with reasonable run-time estimates, reasonable memory-consumption, and assume reasonable start-up datum, something that you could feed to a computer without too much pain. As topics from the top post are answered, they will be erased from the top post to keep clutter low.

So if there are things you want to know -- for example, is there an estimate on how long it would take to compute (?triangulations?) of all finite-volume complete hyperbolic 3-manifolds which have the n-th largest volume (among the volumes of all finite-volume manifolds), where n is the input ordinal? -- add your question to the top post.

Of course, upper bounds on run-times is all I'm looking for. If you know the complexity class on the nose, great. The bias is more towards actual run-times of algorithms you'd consider using.

Let me get the ball rolling. I know answers to a few of these, and I'll try to get around to a few of them in the coming days.

knots and links

• Given a planar diagram for a knot, how expensive is it to compute: the Alexander polynomial, the Jones polynomial, or the HOMFLYPT polynomial? To what extent do these benefit from a quantum computer?

• Given a planar diagram for a knot, how expensive is it to compute a presentation matrix for the Alexander module? How about the Tristram-Levine or Milnor signatures?

• What are the best run-times for unknot recognition, such as (any modified version of) the Haken algorithm? Dynnikov's work on unknot recognition would go here, as well.

• Are there run-time estimates on how long it would take to determine if a knot is slice? ribbon?

3-manifolds

These questions all assume triangulations as input.

• How expensive is 3-sphere recognition? The connect-sum decomposition? (Jaco, Rubinstein, Burton, etc)

• How expensive is the compression-body decomposition, and the JSJ-decomposition?

• How expensive is hyperbolisation (for a triangulated, hyperbolisable 3-manifold) i.e. the closed+cusped Manning algorithm. (Manning, ?Tillman?, others?)

• How expensive is geometrization? (?)

• How expensive is it to compute the Alexander ideals of a triangulated 3-manifold?

• How expensive is it to produce a surgery presentation of a 3-manifold from a triangulation? (D.Thurston and Costantino's work is the closest related to this that I know)

• Given an ordinal $n$ representing the volume of a hyperbolic $3$-manifold of finite volume, I want to know the actual volume (as a real number). How difficult is that to know? How about reconstructing the 3-manifold as well?

• Given a triangulated cusped hyperbolisable $3$-manifold, is there an efficient algorithm to construct the Epstein-Penner decomposition?

4-manifolds

• Given a triangulated rational homology 3-sphere, how expensive is it to compute the generalized Rochlin invariant? (or the Rochlin invariant for a homology 3-sphere)

• Same question, but given a surgery presentation for the rational homology 3-sphere. In this case there is the Kaplan algorithm.

• What computable invariants of Farber-Levine pairings are there, and how hard are they to compute from a surgery presentation of a triangulation of a 4-manifold?

• Is the Oszvath-Szabo ''d''-invariant of $spin^c$ rational homology spheres algorithmically computable now, given a surgery presentation? How are run-times?

Answer 1

The classic paper "The computational complexity of knot and link problems" by Joel Hass, Jeffrey Lagarias, and Nicholas Pippenger [Journal of the ACM 46(2) 185-211 (1999)] established several fundamental complexity results, including showing that determining if a polygonal knot is unknotted is in NP, and that determining the genus of a polygonal knot is in PSPACE. They also provided deterministic algorithms (based on Haken's normal surfaces) for both problems, with exponential worst-case running time bounds.

Answer 2

The Alexander polynomial is calculatable in polynomial time in the number of crossings, as is implemented in the Knot Atlas. So is the Burau representation of links.
I do not know whether the Gassner representation, or the multivariable Alexander polynomial, are calculable in polynomial time. The trick which allows for Gaussian elimination (and therefore polynomial-time calculation of determinants) over $\mathbb{Z}[t^{\pm 1}]$ does not work over $\mathbb{Z}[t_1^{\pm1},\ldots,t_\mu^{\pm 1}]$.

Answer 3

Saul Schleimer proved that sphere recognition lies in NP. See his paper here (n.b. : the version at the arXiv is out of date).