Two results on complexities of decision problems of groups

DOI10.1142/S0218196725500067MaRDI QIDQ7006276zbMATH OpenFDO

Authors Uri Andrews, Matthew Harrison-Trainor, Meng-Che Ho

Publication date 31 March 2025

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0218196725500067

zbMATH Keywords

computably enumerable equivalence relationisomorphism problemword problem

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Hierarchies of computability and definability (03D55) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Review text

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.

Cites work

• A survey on universal computably enumerable equivalence relations
• Analogues of the countable Borel equivalence relations in the setting of computable reducibility
• Classifying word problems of finitely generated algebras via computable reducibility
• Computably enumerable equivalence relations
• Ein Rekursiv Aufzählbarer btt‐Grad, der Nicht Zum Wortproblem Einer Gruppe Gehört
• Finitely generated groups are universal among finitely generated structures
• Finitely Presented Groups with Word Problems of Arbitrary Degrees of Insolubility
• scientific article; zbMATH DE number 3114412 (Why is no real title available?)
• scientific article; zbMATH DE number 3751028 (Why is no real title available?)
• scientific article; zbMATH DE number 3301428 (Why is no real title available?)
• scientific article; zbMATH DE number 3322090 (Why is no real title available?)
• scientific article; zbMATH DE number 3110205 (Why is no real title available?)
• Joins and meets in the structure of ceers
• Jumps of computably enumerable equivalence relations
• On Group-Theoretic Decision Problems and Their Classification. (AM-68)
• On the complexity of the isomorphism relation for finitely generated groups
• Recursive unsolvability of group theoretic problems
• Subgroups of finitely presented groups
• The complexity of index sets of classes of computably enumerable equivalence relations
• Universal computably enumerable equivalence relations
• Word problems and recursively enumerable degrees of unsolvability. A sequel on finitely presented groups
• Über unendliche diskontinuierliche Gruppen.

This page was built for publication: Two results on complexities of decision problems of groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7006276)