Back to Search
Start Over
GENERIC COMPLEXITY OF THE CONJUGACY PROBLEM IN HNN-EXTENSIONS AND ALGORITHMIC STRATIFICATION OF MILLER'S GROUPS.
- Source :
- International Journal of Algebra & Computation; Aug/Sep2007, Vol. 17 Issue 5/6, p963-997, 35p
- Publication Year :
- 2007
-
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 be undecidable. Our results show that "hard" instances of the problem comprise a negligibly small part of the group. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 02181967
- Volume :
- 17
- Issue :
- 5/6
- Database :
- Complementary Index
- Journal :
- International Journal of Algebra & Computation
- Publication Type :
- Academic Journal
- Accession number :
- 74219647
- Full Text :
- https://doi.org/10.1142/S0218196707003913