27
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Can you frame a specific question ? $\endgroup$ – Suresh Venkat May 11 '11 at 4:02
  • 2
    $\begingroup$ 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. $\endgroup$ – Ross Snider May 11 '11 at 4:08
  • 2
    $\begingroup$ Since the outcome might be a list, should this be CW ? $\endgroup$ – Suresh Venkat May 11 '11 at 5:30
  • 5
    $\begingroup$ 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). $\endgroup$ – Peter Shor May 15 '11 at 20:16
  • 3
    $\begingroup$ Have you considered “Algorithmic Topology and Classification of 3-Manifolds” by S.Matveev? (springer.com/mathematics/geometry/book/978-3-540-45898-2 Table of contents available for free download) $\endgroup$ – Artem Pelenitsyn May 16 '11 at 16:14
27
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Jeff. Thank you. This is really good stuff, and incredibly expands the second example. $\endgroup$ – Ross Snider May 11 '11 at 17:03
  • $\begingroup$ 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. $\endgroup$ – Ross Snider May 15 '11 at 20:05
  • $\begingroup$ 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. $\endgroup$ – David Eppstein May 15 '11 at 23:30
  • $\begingroup$ Here's a more careful explanation by Henry Wilton: ldtopology.wordpress.com/2010/01/26/… $\endgroup$ – Jeffε May 16 '11 at 3:40
  • 1
    $\begingroup$ @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? $\endgroup$ – Sam Nead Apr 10 '14 at 14:05

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.