Independence of the conjugacy problem and conjugacy separability

2025/04/16 by Vandeputte, Lukas · 1 citation
#FOS: Mathematics #Group Theory (math.GR)

paper · doi:10.48550/arxiv.2504.12174

Abstract

We construct a class of finitely generated groups which have arbitrarily large conjugacy separability function, but in which the conjugacy problem can be solved in polynomial time, demonstrating that the McKinsey algorithm for the conjugacy problem can have complexity which lies arbitrarily far from the optimum.

Cited by

• Residual finiteness properties of some of Halls groups

Related

• Effective Twisted Conjugacy Separability of Nilpotent Groups
• Effective Separability of Finitely Generated Nilpotent Groups
• The Conjugacy Problem in the Grigorchuk Group is polynomial time decidable
• Generic complexity of the Conjugacy Problem in HNN-extensions and algorithmic stratification of Miller's groups
• Polynomial time conjugacy in wreath products and free solvable groups