« We're doomed | Main | Yippee ya ya, yippee yay! »
December 07, 2005
Comments
The comments to this entry are closed.
Recent Posts
Recent Comments
- 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