The word problem, extreme compression, hydra groups, and magical salmon



Tim Riley

Monday, March 13th, 2017
4:00pm 122 Gates Hall




If G is a group presented by a finite number of generators and relations, the word problem for G asks for an algorithm which, when given a word on the generators, declares whether or not that word represents the identity.  The Dehn function counts how many times you have to call on the defining relators when using them to derive the fact that the given word represents the identity.

It might seem that the Dehn function could be a reasonable measure of the computational complexity of the word problem. This can, in fact, fail dramatically, as I will illustrate with some "hydra" examples.  The main underlying innovation is a means of computing efficiently with enormous integers which are represented in compressed forms by strings of Ackermann functions.

This is joint work with Will Dison and Eduard Einstein.