A new way of classifying word problems
Luca San Mauro
The study of word problems dates back to the work of Dehn in 1911. Given a recursively presented algebra \(A\), the word problem of \(A\) is to decide if two words in the generators of \(A\) refer to the same element. Much is known about the complexity of word problems for familiar algebraic structures: e.g., the Novikov-Boone theorem, one of the most spectacular applications of computability to general mathematics, states that the word problem for finitely presented groups is unsolvable. Yet, the computability theoretic tools commonly employed to measure the complexity of word problems (e.g., Turing or \(m\)-reducibility) are defined for sets, while it is generally acknowledged that many computational facets of word problems emerge only if one interprets them as equivalence relations.
In this work, we revisit the world of word problems, with a special focus on groups and semigroups, through the lens of the theory of equivalence relations, which has grown immensely in recent decades. To do so, we employ computable reducibility, a natural effectivization of Borel reducibility.
This talk collects joint works with Uri Andrews, Valentino Delle Rose, Meng-Che Ho, and Andrea Sorbi.