April 5
Meng-Che 'Turbo' Ho,
California State University at Northridge
Decision problem for groups as equivalence relations
In 1911, Dehn proposed three decision problems for finitely presented groups: the word problem, the conjugacy problem, and the isomorphism problem. These problems have been central to both group theory and logic, and were each proven to be undecidable in the 50's. There is much current research studying the decidability of these problems in certain classes of groups.
Classically, when a decision problem is undecidable, its complexity is measured using Turing reducibility. However, Dehn's problems can also be naturally thought of as computably enumerable equivalence relations (ceers). We take this point of view and measure their complexity using computable reductions. This yields behaviors different from the classical context: for instance, every Turing degree contains a word problem, but not every ceer degree does. This leads us to study the structure of ceer degrees containing a word problem and other related questions.