Computational complexity and the conjugacy problem

DOI10.3233/COM-160060zbMath1378.20048arXiv1605.00598OpenAlexW2345348524MaRDI QIDQ4601028

Paul E. Schupp, Alexei G. Myasnikov

Publication date: 18 January 2018

Published in: Computability (Search for Journal in Brave)

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

zbMATH Keywords

NP-completenessdecidabilityconjugacy problemalgorithmically 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)

Related Items

Partial word and equality problems and Banach densities ⋮ Groups with decidable word problem that do not embed in groups with decidable conjugacy problem