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

The comments to this entry are closed.

- Glencora Borradaile on SIGARCH CARES
- Anonymous Coward on #metoo (Guest Post)
- Whatsinaname on #metoo (Guest Post)
- Atri Rudra on #metoo (Guest Post)
- Jeff Erickson on #metoo (Guest Post)
- Anonymous woman on #metoo (Guest Post)
- David Roberts on #metoo (Guest Post)
- RyanDoughertyAZ on Eight brass monkeys from the ancient, sacred, holy crypts of Egypt
- x on Three talks at SOCG
- GASARCH on SOCG votes to leave ACM

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?

Posted by: Alex Lopez-Ortiz | December 07, 2005 at 03:01 PM

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.

Posted by: JeffE | December 09, 2005 at 04:22 PM

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.

Posted by: | December 10, 2005 at 06:55 PM

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

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

Posted by: JeffE | December 11, 2005 at 09:39 AM

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

Posted by: The Great Gazoo | December 12, 2005 at 07:01 PM