Computational complexity and the conjugacy problem

DOI10.3233/COM-160060zbMATH Open1378.20048arXiv1605.00598OpenAlexW2345348524MaRDI QIDQ4601028FDOQ4601028

Authors: Paul E. Schupp, Alexei Myasnikov 

Publication date: 18 January 2018

Published in: Computability (Search for Journal in Brave)

Abstract: The conjugacy problem for a finitely generated group $G$ is the two-variable problem of deciding for an arbitrary pair $(u,v)$ of elements of $G$, whether or not $u$ is conjugate to $v$ in $G$. We construct examples of finitely generated, computably presented groups such that for every element $u_0$ of $G$, the problem of deciding if an arbitrary element is conjugate to $u_0$ is decidable in quadratic time but the worst-case complexity of the global conjugacy problem is arbitrary: it can be any c.e. Turing degree , can exactly mirror the Time Hierarchy Theorem, or can be $mathcalNP$-complete. Our groups also have the property that the conjugacy problem is generically linear time: that is, there is a linear time partial algorithm for the conjugacy problem whose domain has density $1$, so hard instances are very rare. We also consider the complexity relationship of the "half-conjugacy" problem to the conjugacy problem. In the last section we discuss the extreme opposite situation: groups with algorithmically finite conjugation.

Full work available at URL: https://arxiv.org/abs/1605.00598

Recommendations

• A finitely presented group with almost solvable conjugacy problem.
• GENERIC COMPLEXITY OF THE CONJUGACY PROBLEM IN HNN-EXTENSIONS AND ALGORITHMIC STRATIFICATION OF MILLER'S GROUPS
• Generic-case complexity, decision problems in group theory, and random walks.
• scientific article; zbMATH DE number 3929284

zbMATH Keywords

NP-completenessconjugacy problemdecidabilityalgorithmically finite groupshalf-conjugacyindividual conjugacy problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Cited In (15)

• Title not available (Why is that?)
• The conjugacy problem for Higman’s group
• The conjugacy problem in the Grigorchuk group is polynomial time decidable.
• A family of polycyclic groups over which the uniform conjugacy problem is NP-complete.
• Conjugacy in Baumslag's group, generic case complexity, and division in power circuits
• Groups with decidable word problem that do not embed in groups with decidable conjugacy problem
• A finitely presented group with almost solvable conjugacy problem.
• Polynomial time conjugacy in wreath products and free solvable groups.
• Decision problems, complexity, traces, and representations
• Title not available (Why is that?)
• Partial word and equality problems and Banach densities
• Conjugacy in Miller's groups
• Complexity results on the conjugacy problem for monoids
• Generic-case complexity, decision problems in group theory, and random walks.
• Computational complexity of \(k\)-block conjugacy

This page was built for publication: Computational complexity and the conjugacy problem

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