Two results on complexities of decision problems of groups (Q7006276)

This article studies the isomorphism and word problems for groups from the perspective of computably enumerable equivalence relations (ceers). The central result establishes that the isomorphism problem for recursively presented groups with six generators is \(\Sigma^0_3\)-complete in the ceers hierarchy, i.e., every other \(\Sigma^0_3\) equivalence relation computably reduces to it. The proof uses a fine-grained construction that encodes recursive presentations into algebraic structures, which are then interpreted as groups via small cancellation techniques. This parallels an analogous result in the Borel setting: the isomorphism problem for finitely generated groups is a universal essentially countable Borel equivalence relation [\textit{S. Thomas} and \textit{B. Velickovic}, J. Algebra 217, No. 1, 352--373 (1999;Zbl 0938.03060)].\N\NThe authors also show that the set of ceers equivalent to the word problem of a finitely presented, finitely generated or recursively presented group is itself \(\Sigma^0_3\)-complete. This characterizes such decision problems as maximally complex within this computability-theoretic framework, distinguishing them from earlier classifications based on Turing reducibility. The results provide a clear bridge between algebraic group theory and the structural theory of ceers.