GENERIC COMPLEXITY OF THE CONJUGACY PROBLEM IN HNN-EXTENSIONS AND ALGORITHMIC STRATIFICATION OF MILLER'S GROUPS

DOI10.1142/S0218196707003913MaRDI QIDQ5386949zbMATH OpenOpenAlexFDO

Authors Alexandre V. Borovik, Alexei Myasnikov, Vladimir Remeslennikov

Publication date 14 May 2008

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

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

zbMATH Keywords

algorithmsconjugacy problemHNN-extensionstime complexityword problem

Mathematics Subject Classification ID

Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Analysis of algorithms and problem complexity (68Q25)

Abstract: We discuss time complexity of The Conjugacy Problem in HNN-extensions of groups, in particular, in Miller's groups. We show that for "almost all", in some explicit sense, elements, the Conjugacy Problem is decidable in cubic time. It is worth noting that the Conjugacy Problem in a Miller group may have be undecidable. Our results show that "hard" instances of the problem comprise a negligibly small part of the group.

Recommendations

• Time complexity of the conjugacy problem in relatively hyperbolic groups.
• Huppert's conjecture and almost simple groups
• The Conjugacy Problem for HNN Extensions with Infinite Cyclic Associated Groups
• Conjugacy separability of certain HNN extensions of groups.
• Subgroup separability and conjugacy separability of certain HNN extensions.
• On the complexity of intersection and conjugacy problems in free groups
• On the complexity of the isomorphism relation for finitely generated groups
• Conjugacy separability and outer automorphism groups of certain HNN extensions.
• Conjugacy separability of descending HNN-extensions of finitely generated Abelian groups.
• Conjugacy separability of descending HNN-extensions of finitely generated Abelian groups.

Cites work

• ALMOST EVERY GROUP IS HYPERBOLIC
• An algebraic method for public-key cryptography
• Automatic groups and amalgams
• Average-case complexity and decision problems in group theory.
• Cogrowth of groups and simple random walks
• Generic-case complexity, decision problems in group theory, and random walks.
• scientific article; zbMATH DE number 1186086 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• Hyperbolic groups and free constructions
• MULTIPLICATIVE MEASURES ON FREE GROUPS
• Recursively enumerable degress and the conjugacy problem
• Stallings foldings and subgroups of free groups
• Statistical properties of finitely presented groups

Cited in

(11)

• Amalgamated products of groups: measures of random normal forms.
• Partial word and equality problems and Banach densities
• Random equations in free groups.
• THE CONJUGACY PROBLEM IN AMALGAMATED PRODUCTS I: REGULAR ELEMENTS AND BLACK HOLES
• scientific article; zbMATH DE number 3977255 (Why is no real title available?)
• scientific article; zbMATH DE number 3558084 (Why is no real title available?)
• The Conjugacy Problem for HNN Extensions with Infinite Cyclic Associated Groups
• Random equations in nilpotent groups.
• Computational complexity and the conjugacy problem
• Conjugacy in Miller's groups
• Exponentially generic subsets of groups

This page was built for publication: GENERIC COMPLEXITY OF THE CONJUGACY PROBLEM IN HNN-EXTENSIONS AND ALGORITHMIC STRATIFICATION OF MILLER'S GROUPS

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