<p>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 <a href="https://mathoverflow.net/questions/31821/problems-known-to-be-in-both-np-and-conp-but-not-known-to-be-in-p">comments</a> 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.)  </p>

<p>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.)  </p>

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

<p>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.</p>

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

CC BY-SA 2.5
2010-10-25T12:00:06.377Z
2010-10-25T12:00:06.377Z
2017-04-13T12:57:54.530Z
Sam Nead
<p>This paper shows (though I have not verified it) that 3-sphere recognition* is in coNP assuming GRH:</p>
<blockquote>
<p>Raphael Zentner. <a href="https://arxiv.org/abs/1605.08530" rel="nofollow noreferrer">Integer homology 3-spheres admit irreducible representations in <span class="math-container">$SL(2,\mathbb{C})$</span>.</a> arXiv:1605.08530 [math.GT], 2016</p>
</blockquote>
<p>(Of possible interest: a follow-up paper <a href="http://arxiv.org/abs/1610.04092" rel="nofollow noreferrer">arXiv:1610.04092 [math.GT]</a> uses this to develop an algorithm using Grobner bases.)</p>
<p>*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 <a href="https://arxiv.org/abs/math/0202204" rel="nofollow noreferrer">Kaibel-Pfetsch</a> using <a href="https://epubs.siam.org/doi/10.1137/0218045" rel="nofollow noreferrer">Iliopoulos's 1989 paper &quot;Worst-Case Complexity Bounds on...&quot;</a>), and if the integer homology doesn't match that of a 3-sphere then it's definitely not the 3-sphere.</p>

CC BY-SA 4.0
2017-04-18T17:17:57.713Z
2023-11-01T18:02:07.590Z
2023-11-01T18:02:07.590Z
Joshua Grochow
<p>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.</p>

CC BY-SA 2.5
2010-10-24T19:15:39.880Z
In particular, an NP-hardness result would prove that the 3-sphere cannot be distinguished from other homology 3-spheres in polynomial time.
Jeffε
CC BY-SA 2.5
2010-10-24T03:31:59.990Z
2010-10-24T03:31:59.990Z
Peter Shor 
<p>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"
<a href="http://arxiv.org/abs/math/0407047">arXiv:math/0407047v1 [math.GT]</a>.
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.</p>

CC BY-SA 3.0
2013-12-09T17:30:52.340Z
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.
Arnaud
CC BY-SA 3.0
2017-04-18T17:19:05.440Z
@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 :(.
Joshua Grochow
CC BY-SA 3.0
2017-04-19T09:31:45.827Z
@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.
Arnaud
<cc.complexity-theory><reference-request><open-problem><topology>
Is the 3-sphere recognition problem NP-complete?
Joseph O'Rourke
# Is the 3-sphere recognition problem NP-complete?

(Asked by: username_0 on 2010-10-24)

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]](http://arxiv.org/abs/math/0407047).
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.

**Tags:** cc.complexity-theory, reference-request, open-problem, topology

> **Comments:**
> **username_1**: 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.  
> **username_2**: @username_1: 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 :(.  
> **username_1**: @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.  

---

## 3 answers

### Answer by username_4 on 2010-10-24. Score: 15 | Accepted answer

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.

> **Comments:**
> **username_5**: In particular, an NP-hardness result would prove that the 3-sphere cannot be distinguished from other homology 3-spheres in polynomial time.  

---

### Answer by username_3 on 2010-10-25. Score: 7

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](https://mathoverflow.net/questions/31821/problems-known-to-be-in-both-np-and-conp-but-not-known-to-be-in-p) 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 by username_2 on 2017-04-18. Score: 5

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})$.](https://arxiv.org/abs/1605.08530) arXiv:1605.08530 [math.GT], 2016

(Of possible interest: a follow-up paper [arXiv:1610.04092 [math.GT]](http://arxiv.org/abs/1610.04092) 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](https://arxiv.org/abs/math/0202204) using [Iliopoulos's 1989 paper "Worst-Case Complexity Bounds on..."](https://epubs.siam.org/doi/10.1137/0218045)), and if the integer homology doesn't match that of a 3-sphere then it's definitely not the 3-sphere.


---

