<p>Computational topology encompasses an <em>enormous</em> body of research.  A complete summary of every complexity result would be impossible.  But to give you a small taste, let me expand on your example.</p>

<p>In 1911, Max Dehn posed the <a href="http://en.wikipedia.org/wiki/Word_problem_for_groups" rel="nofollow">word problem</a> for <a href="http://en.wikipedia.org/wiki/Presentation_of_a_group" rel="nofollow">finitely presented groups</a>: Given a string over the generator alphabet, does it represent the identity element?  One year later, Dehn described an algorithm for the word problem in <a href="http://en.wikipedia.org/wiki/Fundamental_group" rel="nofollow">fundamental groups</a> of orientable surfaces; equivalently, Dehn described how to decide whether a given cycle on a given orientable surface is contractible.  Properly implemented, <a href="http://en.wikipedia.org/wiki/Dehn%27s_algorithm#Dehn.27s_algorithm" rel="nofollow">Dehn's algorithm</a> runs in $O(n)$ time.  In the same 1912 paper, Dehn opined that “Solving the word problem for all groups may be as impossible as solving all mathematical problems.”</p>

<p>In 1950, Turing proved that the word problem in finitely presented <a href="http://en.wikipedia.org/wiki/Semigroups" rel="nofollow">semigroups</a> is undecidable, by reduction from the halting problem (surprise, surprise).</p>

<p>Building on Turing's result, Markov proved in 1951 that every nontrivial property of finitely-presented semigroups is undecidable.  A property of groups is nontrivial if some group has the property and some other group does not.  Theoretical computer scientists know the similar result about partial functions as "Rice's Theorem".</p>

<p>In 1952, Novikov proved that the word problem in finitely presented <em>groups</em> is undecidable, thereby proving that Dehn's intuition was correct.  The same result was independently proved by Boone in 1954 and Britton in 1958.</p>

<p>In 1955, Adyan proved that every nontrivial property of finitely-presented <em>groups</em> is undecidable.  The same result was proved independently by Rabin in 1956.  (Yes, <em>that</em> Rabin.)</p>

<p>Finally, in 1958, Markov described algorithms to construct 2-dimensional cell complexes and 4-dimensional manifolds with any desired fundamental group, given the group presentation as input.  This result immediately implied that a huge number of topological problems are undecidable, including the following:</p>

<ul>
<li>Is a given cycle in a given 2-dimensional complex contractible? (This is the word problem.)</li>
<li>Is a given 2-complex simply connected?  ("Is this group trivial?")</li>
<li>Is a given cycle in a given 4-manifold contractible?</li>
<li>Is a given 4-manifold contractible?</li>
<li>Is a given 4-manifold homeomorphic to a particular 4-manifold (constructed by Markov)?</li>
<li>Is a given 5-manifold homeomorphic to the 5-sphere (or any other fixed 5-manifold you choose)?</li>
<li>Is a given 6-complex a manifold?</li>
</ul>

<p>My favorite corollary of these results is more recent and more subtle: <strong>It is undecidable whether a given finitely-presented group is the fundamental group of a 3-manifold.</strong>  Perelman's recent proof of Thurston's geometrization conjecture implies the existence of an algorithm to determine whether a given 3-manifold has a trivial fundamental group.  (As @SamNead points out, results of Rubenstein and Casson imply an algorithm that runs in exponential time.)  If a given group $G$ is not a 3-manifold group, then $G$ cannot be trivial, because $\pi_1(S^3)$ is trivial.  Thus, if you could decide whether $G$ is a 3-manifold group, you could decide whether $G$ is trivial, which is impossible.</p>

CC BY-SA 3.0
2011-05-11T17:03:00.493Z
Jeff. Thank you. This is really good stuff, and incredibly expands the second example.
Ross Snider
CC BY-SA 3.0
2011-05-15T20:05:05.503Z
I have added a bounty to the question not because this answer isn't amazing, but because I am looking to encourage more answers (especially more like my first example). Thanks again.
Ross Snider
CC BY-SA 3.0
2011-05-15T23:30:12.317Z
Your argument for undecidability of being a 3-manifold group seems a little shaky to me. It prevents you from being able to construct a 3-manifold for which G is the group, but maybe there is some way of answering yes or no without constructing the manifold? Then Perelman wouldn't have anything to go on.
David Eppstein
CC BY-SA 3.0
2011-05-16T03:40:37.740Z
Here's a more careful explanation by Henry Wilton: http://ldtopology.wordpress.com/2010/01/26/3-manifold-groups-are-known-right/
Jeffε
CC BY-SA 3.0
2011-05-16T03:50:24.660Z
Neuwirth described an algorithm to construct a 3-manifold with a given fundamental group, if such a 3-manifold exists, in 1968: http://journals.cambridge.org/abstract_S0305004100043279.  Also, the undecidability of  3-manifold group recognition does not actually require geometrization; John Stallings gave a self-contained proof in 1962.
Jeffε
CC BY-SA 3.0
2012-04-18T21:40:58.650Z
Unknot recognition would be a nice addition to your list.  For embeddings of $S^n$ into $S^{n+2}$: if $n = 1$ then the problem is decidable (Haken) and in NP (Hass, Lagarias, and Pippenger).  If $n > 2$ then the problem is undecidable (Nabutovsky and Weinberger).  For $n = 2$ the unknotting problem is still open!
Sam Nead
CC BY-SA 3.0
2014-04-09T16:09:08.537Z
"Is a given 2-complex simply connected" is undecidable for the reasons given here. However, it is not obvious that it implies anything about deciding if a 2-complex is contractible.
Marc Glisse
CC BY-SA 3.0
2014-04-09T21:52:27.890Z
@MarcGlisse: Good point; fixed.
Jeffε
CC BY-SA 3.0
2014-04-10T14:05:05.500Z
@JeffE - I'm not sure why you ignored my previous comment.  There _is_ an exp-time algorithm to decide if the fundamental group of a (closed connected) three-manifold is trivial.  Saying "NO bounds are known on the complexity of this algorithm" is wrong... isn't it?  What am I missing?  Can I please ask you to explain?
Sam Nead
CC BY-SA 3.0
2014-01-31T12:22:27.057Z
@JeffE - "Perelman's recent proof [snip]. (This is a pure existence argument; apparently NO bounds are known on the complexity of this algorithm.)" --- I think this is not correct.  Perelman proves the Poincare conjecture - thus a closed three-manifold $M$ has trivial fundamental group if and only if $M$ is homeomorphic to the three-sphere.  There is a simply exponential algorithm (due to Rubinstein, with running time analysis due to Casson) that recognizes the three-sphere.
Sam Nead
CC BY-SA 3.0
2011-05-11T06:33:38.633Z
2014-04-11T01:07:50.770Z
2014-04-11T01:07:50.770Z
Jeffε
<p>Ryan Budney has started similar discussions at MathOverFlow: </p>

<p><a href="https://mathoverflow.net/questions/35946/how-expensive-is-knowledge-knots-links-3-and-4-manifold-algorithms">https://mathoverflow.net/questions/35946/how-expensive-is-knowledge-knots-links-3-and-4-manifold-algorithms</a></p>

<p><a href="https://mathoverflow.net/questions/144158/what-is-the-state-of-the-art-for-algorithmic-knot-simplification/145927">https://mathoverflow.net/questions/144158/what-is-the-state-of-the-art-for-algorithmic-knot-simplification/145927</a></p>

<p>and at Wikipedia: </p>

<p><a href="http://en.wikipedia.org/wiki/Talk:Computational_topology" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Talk:Computational_topology</a></p>

CC BY-SA 3.0
2014-01-31T12:28:47.007Z
2014-01-31T12:37:48.973Z
2017-04-13T12:57:54.777Z
Sam Nead
<p>I am a computer scientist taking a course on Topology (a sprinkling of point-set topology heavily flavored with continuum theory). I have become interested in decision problems testing a description of a space (by simplices) for topological properties; those preserved up to homeomorphism.</p>

<p>It is known, for example, that determining the genus of a knot is in PSPACE and is NP-Hard. (Agol 2006; Hass, Lagarias, Pippenger 1999)</p>

<p>Other results have more a more general feel: A. A. Markov (the son of <em>the</em> Markov) showed in 1958 that testing two spaces for a homeomorphism in dimensions $5$ or higher is undecidable (by showing the undecidability for 4-manifolds). Unfortunately, this last example is not a perfect exemplar of my question, as it deals with the homeomorphy problem itself rather than properties preserved under homeomorphism.</p>

<p>There seems to be a large amount of work in "low dimensional topology": knot and graph theory. I am definitely interested in results from low dimensional topology, but am more interested in generalized results (these seem to be rare).</p>

<p>I am most interested in problems which are NP-Hard on average, but feel encouraged to list problems not known to be so.</p>

<blockquote>
  <p>What results are known about the computational complexity of topological properties?</p>
</blockquote>

CC BY-SA 3.0
2011-05-11T04:02:06.250Z
Can you frame a specific question ?
Suresh Venkat
CC BY-SA 3.0
2011-05-11T04:08:53.393Z
Before someone raises the objection, let me defend why I believe this question is specific: I performed the usual literature search and found relatively little addressing my question. Therefore, answers to the question involve a certain level of expertise. Furthermore, computational topology is indisputably on topic in this TCS SE.
Ross Snider
CC BY-SA 3.0
2011-05-11T05:30:11.593Z
Since the outcome might be a list, should this be CW ?
Suresh Venkat
CC BY-SA 3.0
2011-05-11T17:00:19.133Z
Suresh - I am not against the idea of CW. I don't know how to set the question as CW.
Ross Snider
CC BY-SA 3.0
2011-05-15T20:16:47.650Z
I think this is a great question. There is very little known about computational complexity of topology problems, and I don't believe it's been collected in one place (if it has, one answer will suffice, and the question shouldn't be CW).
Peter Shor 
CC BY-SA 3.0
2011-05-16T16:14:50.620Z
Have you considered “Algorithmic Topology and Classification of 3-Manifolds” by S.Matveev? (http://www.springer.com/mathematics/geometry/book/978-3-540-45898-2 Table of contents available for free download)
Artem Pelenitsyn
CC BY-SA 3.0
2011-05-18T13:59:49.410Z
@Artem I have not. It seems very relevant. Thank you for the link.
Ross Snider
CC BY-SA 3.0
2014-01-31T20:35:04.450Z
any tiein to [GCT](http://en.wikipedia.org/wiki/Geometric_complexity_theory)? lots of stuff on that
vzn
<cc.complexity-theory><big-list><topology>
Complexity of Topological Properties.
Ross Snider
# Complexity of Topological Properties.

(Asked by: username_0 on 2011-05-11)

I am a computer scientist taking a course on Topology (a sprinkling of point-set topology heavily flavored with continuum theory). I have become interested in decision problems testing a description of a space (by simplices) for topological properties; those preserved up to homeomorphism.

It is known, for example, that determining the genus of a knot is in PSPACE and is NP-Hard. (Agol 2006; Hass, Lagarias, Pippenger 1999)

Other results have more a more general feel: A. A. Markov (the son of *the* Markov) showed in 1958 that testing two spaces for a homeomorphism in dimensions $5$ or higher is undecidable (by showing the undecidability for 4-manifolds). Unfortunately, this last example is not a perfect exemplar of my question, as it deals with the homeomorphy problem itself rather than properties preserved under homeomorphism.

There seems to be a large amount of work in "low dimensional topology": knot and graph theory. I am definitely interested in results from low dimensional topology, but am more interested in generalized results (these seem to be rare).

I am most interested in problems which are NP-Hard on average, but feel encouraged to list problems not known to be so.

> What results are known about the computational complexity of topological properties?

**Tags:** cc.complexity-theory, big-list, topology

> **Comments:**
> **username_1**: Can you frame a specific question ?  
> **username_0**: Before someone raises the objection, let me defend why I believe this question is specific: I performed the usual literature search and found relatively little addressing my question. Therefore, answers to the question involve a certain level of expertise. Furthermore, computational topology is indisputably on topic in this TCS SE.  
> **username_1**: Since the outcome might be a list, should this be CW ?  
> **username_0**: Suresh - I am not against the idea of CW. I don't know how to set the question as CW.  
> **username_2**: I think this is a great question. There is very little known about computational complexity of topology problems, and I don't believe it's been collected in one place (if it has, one answer will suffice, and the question shouldn't be CW).  
> **username_3**: Have you considered “Algorithmic Topology and Classification of 3-Manifolds” by S.Matveev? (http://www.springer.com/mathematics/geometry/book/978-3-540-45898-2 Table of contents available for free download)  
> **username_0**: @Artem I have not. It seems very relevant. Thank you for the link.  
> **username_4**: any tiein to [GCT](http://en.wikipedia.org/wiki/Geometric_complexity_theory)? lots of stuff on that  

---

## 2 answers

### Answer by username_5 on 2011-05-11. Score: 27

Computational topology encompasses an *enormous* body of research. A complete summary of every complexity result would be impossible. But to give you a small taste, let me expand on your example.

In 1911, Max Dehn posed the [word problem](http://en.wikipedia.org/wiki/Word_problem_for_groups) for [finitely presented groups](http://en.wikipedia.org/wiki/Presentation_of_a_group): Given a string over the generator alphabet, does it represent the identity element? One year later, Dehn described an algorithm for the word problem in [fundamental groups](http://en.wikipedia.org/wiki/Fundamental_group) of orientable surfaces; equivalently, Dehn described how to decide whether a given cycle on a given orientable surface is contractible. Properly implemented, [Dehn's algorithm](http://en.wikipedia.org/wiki/Dehn%27s_algorithm#Dehn.27s_algorithm) runs in $O(n)$ time. In the same 1912 paper, Dehn opined that “Solving the word problem for all groups may be as impossible as solving all mathematical problems.”

In 1950, Turing proved that the word problem in finitely presented [semigroups](http://en.wikipedia.org/wiki/Semigroups) is undecidable, by reduction from the halting problem (surprise, surprise).

Building on Turing's result, Markov proved in 1951 that every nontrivial property of finitely-presented semigroups is undecidable. A property of groups is nontrivial if some group has the property and some other group does not. Theoretical computer scientists know the similar result about partial functions as "Rice's Theorem".

In 1952, Novikov proved that the word problem in finitely presented *groups* is undecidable, thereby proving that Dehn's intuition was correct. The same result was independently proved by Boone in 1954 and Britton in 1958.

In 1955, Adyan proved that every nontrivial property of finitely-presented *groups* is undecidable. The same result was proved independently by Rabin in 1956. (Yes, *that* Rabin.)

Finally, in 1958, Markov described algorithms to construct 2-dimensional cell complexes and 4-dimensional manifolds with any desired fundamental group, given the group presentation as input. This result immediately implied that a huge number of topological problems are undecidable, including the following:

* Is a given cycle in a given 2-dimensional complex contractible? (This is the word problem.)
* Is a given 2-complex simply connected? ("Is this group trivial?")
* Is a given cycle in a given 4-manifold contractible?
* Is a given 4-manifold contractible?
* Is a given 4-manifold homeomorphic to a particular 4-manifold (constructed by Markov)?
* Is a given 5-manifold homeomorphic to the 5-sphere (or any other fixed 5-manifold you choose)?
* Is a given 6-complex a manifold?

My favorite corollary of these results is more recent and more subtle: **It is undecidable whether a given finitely-presented group is the fundamental group of a 3-manifold.** Perelman's recent proof of Thurston's geometrization conjecture implies the existence of an algorithm to determine whether a given 3-manifold has a trivial fundamental group. (As @SamNead points out, results of Rubenstein and Casson imply an algorithm that runs in exponential time.) If a given group $G$ is not a 3-manifold group, then $G$ cannot be trivial, because $\pi\_1(S^3)$ is trivial. Thus, if you could decide whether $G$ is a 3-manifold group, you could decide whether $G$ is trivial, which is impossible.

> **Comments:**
> **username_0**: Jeff. Thank you. This is really good stuff, and incredibly expands the second example.  
> **username_0**: I have added a bounty to the question not because this answer isn't amazing, but because I am looking to encourage more answers (especially more like my first example). Thanks again.  
> **username_6**: Your argument for undecidability of being a 3-manifold group seems a little shaky to me. It prevents you from being able to construct a 3-manifold for which G is the group, but maybe there is some way of answering yes or no without constructing the manifold? Then Perelman wouldn't have anything to go on.  
> **username_5**: Here's a more careful explanation by Henry Wilton: http://ldtopology.wordpress.com/2010/01/26/3-manifold-groups-are-known-right/  
> **username_5**: Neuwirth described an algorithm to construct a 3-manifold with a given fundamental group, if such a 3-manifold exists, in 1968: http://journals.cambridge.org/abstract_S0305004100043279.  Also, the undecidability of  3-manifold group recognition does not actually require geometrization; John Stallings gave a self-contained proof in 1962.  
> **username_7**: Unknot recognition would be a nice addition to your list.  For embeddings of $S^n$ into $S^{n+2}$: if $n = 1$ then the problem is decidable (Haken) and in NP (Hass, Lagarias, and Pippenger).  If $n > 2$ then the problem is undecidable (Nabutovsky and Weinberger).  For $n = 2$ the unknotting problem is still open!  
> **username_7**: @JeffE - "Perelman's recent proof [snip]. (This is a pure existence argument; apparently NO bounds are known on the complexity of this algorithm.)" --- I think this is not correct.  Perelman proves the Poincare conjecture - thus a closed three-manifold $M$ has trivial fundamental group if and only if $M$ is homeomorphic to the three-sphere.  There is a simply exponential algorithm (due to Rubinstein, with running time analysis due to Casson) that recognizes the three-sphere.  
> **username_8**: "Is a given 2-complex simply connected" is undecidable for the reasons given here. However, it is not obvious that it implies anything about deciding if a 2-complex is contractible.  
> **username_5**: @MarcGlisse: Good point; fixed.  
> **username_7**: @JeffE - I'm not sure why you ignored my previous comment.  There _is_ an exp-time algorithm to decide if the fundamental group of a (closed connected) three-manifold is trivial.  Saying "NO bounds are known on the complexity of this algorithm" is wrong... isn't it?  What am I missing?  Can I please ask you to explain?  

---

### Answer by username_7 on 2014-01-31. Score: 3

Ryan Budney has started similar discussions at MathOverFlow:

<https://mathoverflow.net/questions/35946/how-expensive-is-knowledge-knots-links-3-and-4-manifold-algorithms>

<https://mathoverflow.net/questions/144158/what-is-the-state-of-the-art-for-algorithmic-knot-simplification/145927>

and at Wikipedia:

<http://en.wikipedia.org/wiki/Talk:Computational_topology>


---

