Two results on complexities of decision problems of groups

2024/03/04 by Uri Andrews, Andrews, Uri, Matthew Harrison‐Trainor +3
Mathematics · #03D40 #03D55 #20F10 #FOS: Mathematics #Graph theory and applications #Group Theory (math.GR) #Logic (math.LO)

paper · pdf · doi:10.48550/arxiv.2403.02492

openalex publication_date 2024/03/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We answer two questions on the complexities of decision problems of groups, each related to a classical result. First, C. Miller characterized the complexity of the isomorphism problem for finitely presented groups in 1971. We do the same for the isomorphism problem for recursively presented groups. Second, the fact that every Turing degree appears as the degree of the word problem of a finitely presented group is shown independently by multiple people in the 1960s. We answer the analogous question for degrees of ceers instead of Turing degrees. We show that the set of ceers which are computably equivalent to a finitely presented group is Σ⁰₃-complete, which is the maximal possible complexity.

Related

• Remarks and problems about algorithmic descriptions of groups
• A Finitely presented group whose word problem has sampleable hard instances
• Complexity of some algorithmic problems in groups: a survey
• Decision problems and profinite completions of groups
• Decision problems for finite and infinite presentations of groups and monoids