Is the 3-sphere recognition problem NP-complete?

Question

It is known that determining whether or not a given triangulated 3-manifold is a 3-sphere is in NP, via work by Saul Schleimer in 2004: "Sphere recognition lies in NP" arXiv:math/0407047v1 [math.GT]. I am wondering if this has been established to be NP-complete in the last five or six years? Analogous problems, such as the 3-manifold knot genus problem, have been shown NP-complete.

Answer 1

If it's NP-complete, then wouldn't you have proved that no set of (uniformly) polynomial-time computable invariants of 3-manifolds distinguishes 3-spheres from other 3-manifolds. I would be very surprised if this is known.

Answer 2

Just to add to Peter's answer: the unknotting problem for knots in the three-sphere was shown to be in NP by Hass, Lagarias, and Pippenger. Ian Agol has proven that the unknotting problem is in co-NP (but see his comments on MathOverflow). It feels, at least to me, that the three-sphere recognition problem is much more akin to unknotting than to knot genus in general three-manifolds. (Because it is certified by the presence of a positive Euler characteristic surface.)

Thus I would wager that three-sphere recognition is also in co-NP. A step in this direction would be to show that recognition of irreducible, toroidal manifolds is in NP, directly following Agol. Slightly stronger would be to show that Haken manifold recognition lies in NP. Separating the three-sphere from the irreducible, non-toroidal manifolds is more difficult. But perhaps the thing to do there is use Geometrization - if the manifold is closed, orientable, irreducible and atoroidal then it has one of the eight Thurston geometries. Perhaps it is easy to certify all of the geometric but non-hyperbolic manifolds, say via almost normal Heegaard splittings. (Although the complexity bounds of Hass, Lagarias, and Pippenger would have to be replaced, somehow.)

Certifying that a three-manifold $M$ has a hyperbolic structure sounds harder. Two ideas suggest themselves:

Following ideas of Gabai (and of course Thurston) one might look for the correct simple closed curve to drill out of $M$, to get a manifold $N$ with torus boundary. Certifying the hyperbolic structure of $N$ is much easier and one might even be able to record enough information to prove that filling $N$ to get $M$ back doesn't destroy hyperbolicity.

A much less reasonable approach is to prove the virtual Haken conjecture in such a way that you either a) get polynomial-sized bounds on the degree of the cover or b) learn something incredibly useful about $M$.

Answer 3

This paper shows (though I have not verified it) that 3-sphere recognition* is in coNP assuming GRH:

Raphael Zentner. Integer homology 3-spheres admit irreducible representations in $SL(2,\mathbb{C})$. arXiv:1605.08530 [math.GT], 2016

(Of possible interest: a follow-up paper arXiv:1610.04092 [math.GT] uses this to develop an algorithm using Grobner bases.)

*Technically it's stated that recognizing the 3-sphere among integer homology 3-spheres is in coNP assuming GRH. One can compute the integer homology given a triangulation in poly-time using Smith normal form (this is discussed in Problem 33 of Kaibel-Pfetsch using Iliopoulos's 1989 paper "Worst-Case Complexity Bounds on..."), and if the integer homology doesn't match that of a 3-sphere then it's definitely not the 3-sphere.