Calibrating word problems of groups via the complexity of equivalence relations

André Nies, Andrea Sorbi

(1) There is a finitely presented group with a word problem which is a uniformly effectively inseparable equivalence relation. (2) There is a finitely generated group of computable…