13
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ The problem is now know to also be in co-NP, see the announcement in J. Hass, New results on the complexity of recognizing the 3-sphere, Oberwolfach Rep. 9 (2012), no. 2, 1425{1426. $\endgroup$ – Arnaud Dec 9 '13 at 17:30
  • $\begingroup$ @Arnaud: Any update on this? I couldn't find anything from Hass since then on the problem. The best I could find is the coNP result conditioned on GRH that I put in my new answer, and that seems to make no mention of Hass :(. $\endgroup$ – Joshua Grochow Apr 18 '17 at 17:19
  • $\begingroup$ @JoshuaGrochow Sorry, my comment was inaccurate and that claim by Joel Hass (I also forgot to say that this was with G. Kuperberg) was assuming GRH as well. As far as I know, a complete write-up has not appeared yet. $\endgroup$ – Arnaud Apr 19 '17 at 9:31
15
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ In particular, an NP-hardness result would prove that the 3-sphere cannot be distinguished from other homology 3-spheres in polynomial time. $\endgroup$ – Jeffε Oct 24 '10 at 19:15
7
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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. I'm not an expert in this area, but it seems clear to me that one can compute the integer homology given a triangulation in poly-time, and if the integer homology doesn't match that of a 3-sphere then it's definitely not the 3-sphere.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.