Complexity of Topological Properties. 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?
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 for finitely presented groups: 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 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 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 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.