« We're doomed | Main | Yippee ya ya, yippee yay! »

December 07, 2005


Alex Lopez-Ortiz

What is the relationship, if any, of splitting cycles and the result of Koutsoupias that determining if a cycle on a surface is homeomorphic to a point is non-decidable?


First, it's not Koutsoupias's result, but rather a direct consequence of the undecidability of the word problem for general groups, which was proved by Novikov and Boone in the 1950s.

Second, the result applies to cycles in arbitrary 2-dimensional simplicial complexes. The contractibility problem for cycles on SURFACES was proved decidable by Dehn circa 1910.

Boy, that answer seems to have a bit of an edge.

It was an honest question, as it seems to me that a splitting cycle and a cycle which is not homeomorphic to a point are not exactly the same thing: isn't it the case that all splitting cycles are non-homeorphic to a point but the converse is not necesarily true?

p.s Novikov's result is right. I first read about in a paper on distributed computation by Koutsoupias quite a while back. That's how I got them mixed up.


"Boy, that answer seems to have a bit of an edge."

Sorry... It's been a long semester.

The Great Gazoo

How is what you do as a computational geometer different than what a topologist does? Or is it different?

The comments to this entry are closed.