Group word problems revisited

Abstract: Pre-dating computability theory, Max Dehn proposed to find algorithms to answer, for a given group presentation, word problem of the group: whether two given words in the generators are equal in the group. Novikov and Boone showed in the 50s that some simply presented groups can have undecidable word problem. In fact, every r.e. degree contains the word problem of a finitely presented group. From the perspective of the Turing degrees, this gives a complete answer to the question of the complexity of word problems of groups. The answer is: Every possible complexity.

I will present a different perspective on studying word problem complexity: We study the complexity of word problems as equivalence relations under computable reducibility. That is, we say that an equivalence relation R reduces to an equivalence relation E if there is a computable function f so that xRy if and only if f(x) E f(y). In this structure, we find a more subtle picture, beginning with the fact that not every degree is the degree of a the word problem of a group. Some surprising phenomena appear. Work joint with Turbo Ho and Luca San Mauro.

group theorylogic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic